Sudoku Solver

Board.java

package sudoku;

import java.util.Arrays;

/**
 * This class is a DataStructure to store the board
 * It's also offers method to get particular areas of the board and to retrieve/set values
 * Visibility is package-friendly as it is part of the "internals" of the Solver
 * 
 * @author vincent
 */
final class Board {
	// Constants with package visibility
	static final int EMPTY_CELL = 0;
	static final int GRID_SIZE = 9;
	static final int REGION_SIZE = 3;
	static final String ERROR_MSG_SIZE = "Please provide a "+ GRID_SIZE +"x" + GRID_SIZE + " array for Input";

	private final int[][] board;
	private char[] line;

	/**
	 * Default Constructor
	 * @param init a dimension 2 array of integers, empty cells are represented by 0
	 */
	Board(int[][] init) {
		// A check on the size of the input data could be done here, to throw an InvalidInputException
		// Also, it is possible to deep copy the input array to ensure isolation/security.
		board = init;
	}
	/**
	 * Returns the specified row
	 * @param row row number (starting from 0)
	 */
	int[] getRow(int row) {
		return board[row];
	}

	/**
	 * Returns the specified column
	 * @param col column number (starting from 0)
	 */
	int[] getColumn(int col) {
		final int[] columnView = new int[GRID_SIZE];
		for(int a = 0; a < GRID_SIZE; a++) {
			columnView[a] = board[a][col];
		}
		return columnView;
	}

	/**
	 * Return the numbers from an area of the board (classically a 3x3 square)
	 * @param row row number 
	 * @param col column number
	 * @return the area that enclose the specified row/col values
	 */
	int[] getRegion(int row, int col) {
		final int[] regionView = new int[GRID_SIZE];
		final int rowBase = row - (row % REGION_SIZE);
		final int colBase = col - (col % REGION_SIZE);
		int counter = 0;
		// REGION_SIZE (3) Rows/Columns from rowBase/ColumnBase
		for (int r = rowBase; r < REGION_SIZE + rowBase; r++) {
			for (int c = colBase ; c < REGION_SIZE + colBase; c++) {
				regionView[counter++] = board[r][c];
			}
		}
		return regionView;
	}

	/**
	 * Getter
	 */
	int getCell(int row, int col) {
		return board[row][col];
	}

	/**
	 * Setter
	 */
	void setCell(int row, int col, int val) {
		board[row][col] = val;
	}

	/**
	 * Return a string containing the sudoku with region separators
	 */
	@Override
	public String toString() {
		// Exact size of the generated string for the buffer (values + spacers)
		final int size = (GRID_SIZE*2+1+((REGION_SIZE+1)*2))*(GRID_SIZE+REGION_SIZE+1);
		final String verticalSpace = " |";
		// A StringBuilder is absolutely needed here
		// use of String concatenation (+) would have really bad performance
		final StringBuilder buffer = new StringBuilder(size);
		// Row/Column traversal
		for (int a=0; a < GRID_SIZE; a++) {
			int[] row = board[a];
			if (a % REGION_SIZE == 0) {
				appendLine(buffer);
			}
			for (int b=0; b < GRID_SIZE; b++) {
				int value = row[b];
				if (b % REGION_SIZE == 0) {
					buffer.append(verticalSpace);
				}
				appendValue(buffer, value);
			}
			buffer.append(verticalSpace);
			buffer.append('\n');
		}
		appendLine(buffer);
		return buffer.toString();
	}

	/**
	 * Appends the value, or a _ if empty
	 */
	private void appendValue(StringBuilder buffer, int value) {
		buffer.append(' ');
		if (value != EMPTY_CELL) {
			buffer.append(value);
		} else {
			buffer.append('_');
		}
	}
	/**
	 * Append a line (separator between region)
	 */
	private void appendLine(StringBuilder buffer) {
		// Only create the line once 
		// Thread safe because the Sudoku class create one new Board for every toString() method call
		if (line == null) {
		  line = new char[GRID_SIZE*2+((REGION_SIZE+1)*2)];
		  Arrays.fill(line, '-');
		  //first char as space
		  line[0] = ' ';
		}
		buffer.append(line);
		buffer.append('\n');
	}
}

Main.java

import sudoku.Sudoku;

/**
 * Main class
 * As, it is in another package, it has only the visibility on the Sudoku "API" class
 * This design enforce maintainability as the internals of the Solvers are not externally accessible.
 * 
 * Thus, Sudoku internal classes could evolve, without breaking client compatibility.
 */
public class Main {
	public static void main(String[] args) {
		// Here, input args parsing is possible to enable passing a sudoku as a CLI argument
		// It would have involved to parse 81 Integer and to generate a 9x9 array
		
		//Very hard sudoku (lot of 0)
		final int[][] sudoku = {
			{8,6,0,0,2,0,0,0,0},
			{0,0,0,7,0,0,0,5,9},
			{0,0,0,0,0,0,0,0,0},
			{0,0,0,0,6,0,8,0,0},
			{0,4,0,0,0,0,0,0,0},
			{0,0,5,3,0,0,0,0,7},
			{0,0,0,0,0,0,0,0,0},
			{0,2,0,0,0,0,6,0,0},
			{0,0,7,5,0,9,0,0,0}
		};
		// Print input sudoku
		System.out.println(Sudoku.asString(sudoku));
		// If sudoku sucessfuly solved
		if (Sudoku.solve(sudoku)) {
			//Print solved sudoku
			System.out.println(Sudoku.asString(sudoku));
		}
		
	}
}

output

 -------------------------
 | 8 6 _ | _ 2 _ | _ _ _ |
 | _ _ _ | 7 _ _ | _ 5 9 |
 | _ _ _ | _ _ _ | _ _ _ |
 -------------------------
 | _ _ _ | _ 6 _ | 8 _ _ |
 | _ 4 _ | _ _ _ | _ _ _ |
 | _ _ 5 | 3 _ _ | _ _ 7 |
 -------------------------
 | _ _ _ | _ _ _ | _ _ _ |
 | _ 2 _ | _ _ _ | 6 _ _ |
 | _ _ 7 | 5 _ 9 | _ _ _ |
 -------------------------

 -------------------------
 | 8 6 3 | 9 2 5 | 7 4 1 |
 | 4 1 2 | 7 8 6 | 3 5 9 |
 | 7 5 9 | 4 1 3 | 2 8 6 |
 -------------------------
 | 9 7 1 | 2 6 4 | 8 3 5 |
 | 3 4 6 | 8 5 7 | 9 1 2 |
 | 2 8 5 | 3 9 1 | 4 6 7 |
 -------------------------
 | 1 9 8 | 6 3 2 | 5 7 4 |
 | 5 2 4 | 1 7 8 | 6 9 3 |
 | 6 3 7 | 5 4 9 | 1 2 8 |
 -------------------------

Solver.java

package sudoku;
import static sudoku.Board.EMPTY_CELL;
import static sudoku.Board.GRID_SIZE;

/**
 * This class implements the solving algorithm, It is separated from
 * the board logic
 * 
 * The visibility of this class is package, as it is not the external API
 * @author vincent
 *
 */
class Solver {

	private final Board board;

	/**
	 * Constructor
	 * @param input a 9x9 array representing a sudoku, empty cells are 0
	 */
	Solver(int[][] input) {
		this.board = new Board(input);
	}
	/**
	 * Method to solve the sudoku "in-place" (without creating/copying with a new array)
	 * @return true if the sudoku is successfully solved
	 */
	boolean solve() {
		return solve(0,0);
	}

	/**
	 * Returns the board object, useful for pretty-printing of the sudoku
	 */
	Board getBoard() {
		return board;
	}
	
	/**
	 * Backtracking recursive algorithm to solve sudoku
	 */
	private boolean solve(int row, int col) {
		if (row == GRID_SIZE) {
			row = 0;
			if (++col == GRID_SIZE) {
				return true;
			}
		}
		if (board.getCell(row, col) != EMPTY_CELL) {
			return solve(row+1,col);
		}
		// For all possible values
		for(int val = 1; val <= GRID_SIZE; val++) {
			if (isMoveOK(row, col, val)) {
				board.setCell(row, col, val);
				if (solve(row+1, col)) {
					return true;
				}
			}
		}
		// Reset the cell to EMPTY to do recursive backtrack and try again
		board.setCell(row, col, EMPTY_CELL);
		return false;
	}


	private boolean isMoveOK(int row, int col, int val) {
		return ! (  arrayContains(board.getRow(row), val)
				|| arrayContains(board.getColumn(col), val)
				|| arrayContains(board.getRegion(row, col), val));
	}

	private boolean arrayContains(int[] array, int val) {
		for (int arrayVal : array) {
			if (arrayVal == val) {
				// return true and stop the iteration
				return true;
			}
		}
		return false;
	}
}

Sudoku.java

package sudoku;

/**
 * Sudoku External API (only public class of the package)
 */
public class Sudoku 
{	
	/**
	 * Solves "in-place" the sudoku in the provided array
	 * this method signature is inspired from the JDK method Arrays.sort(int[] array) 
	 * @param sudoku a 9x9 array representing a sudoku, empty cells are 0
	 * @return true if the sudoku has been sucessfully solved
	 */
	public static boolean solve(int[][] sudoku) {
	  return new Solver(sudoku).solve();	
	}
	
	/**
	 * Returns the sudoku board as a string
	 * @param sudoku a 9x9 array representing a sudoku, empty cells are 0
	 * @return a string representation of the sudoku
	 */
	public static String asString(int[][] sudoku) {
	  return new Board(sudoku).toString();	
	}
}