SudokuSolver.java

import java.util.ArrayList;

public class SudokuSolver {
	private class Coord {
		public int row;
		public int col;

		public Coord(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}

	private class Sudoku {
		public boolean[][] rowStatus = new boolean[9][9];
		public boolean[][] colStatus = new boolean[9][9];
		public boolean[][] blockStatus = new boolean[9][9];
		public int[][] startInds = new int[9][9]; // start index on each cell
													// for nextSuitableNumber
		public ArrayList<Coord> emptyCells = new ArrayList<Coord>();

		public Sudoku(char[][] board) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					if (board[i][j] != '.') {
						rowStatus[i][board[i][j] - '0' - 1] = true;
						colStatus[j][board[i][j] - '0' - 1] = true;
						blockStatus[getBlockInd(i, j)][board[i][j] - '0' - 1] = true;
					} else {
						emptyCells.add(new Coord(i, j));
					}
				}
			}
		}

		private int getBlockInd(int row, int col) {
			if ((row >= 0 && row <= 2) && (col >= 0 && col <= 2))
				return 0;
			if ((row >= 3 && row <= 5) && (col >= 0 && col <= 2))
				return 1;
			if ((row >= 6 && row <= 8) && (col >= 0 && col <= 2))
				return 2;
			if ((row >= 0 && row <= 2) && (col >= 3 && col <= 5))
				return 3;
			if ((row >= 3 && row <= 5) && (col >= 3 && col <= 5))
				return 4;
			if ((row >= 6 && row <= 8) && (col >= 3 && col <= 5))
				return 5;
			if ((row >= 0 && row <= 2) && (col >= 6 && col <= 8))
				return 6;
			if ((row >= 3 && row <= 5) && (col >= 6 && col <= 8))
				return 7;
			return 8;
		}

		public void update(int row, int col, char val, boolean isUndo) {
			boolean status = isUndo ? false : true;
			rowStatus[row][val - '0' - 1] = status;
			colStatus[col][val - '0' - 1] = status;
			blockStatus[getBlockInd(row, col)][val - '0' - 1] = status;
		}

		public char nextSuitableNumber(int row, int col) {
			char target = '.';
			char tmp;
			int startInd = startInds[row][col];
			for (int i = startInd; i < 9; i++) {
				tmp = (char) ('1' + i);
				if (rowStatus[row][i])
					continue;
				if (colStatus[col][i])
					continue;
				if (blockStatus[getBlockInd(row, col)][i])
					continue;
				target = tmp;
				startInds[row][col] = i + 1;
				break;
			}
			if (target == '.')
				startInds[row][col] = 0;
			return target;
		}
	}

	public void solveSudoku(char[][] board) {
		Sudoku sd = new Sudoku(board);
		solveSudoku(board, sd);
	}

	private void solveSudoku(char[][] board, Sudoku sd) {
		int i = 0;
		int numOfEmptyCells = sd.emptyCells.size();
		int row = 0;
		int col = 0;
		while (true) {
			row = sd.emptyCells.get(i).row;
			col = sd.emptyCells.get(i).col;
			char candidate = sd.nextSuitableNumber(row, col);
			if (candidate == '.') {
				if (isOutOfBound(--i, numOfEmptyCells))
					return;
				Coord previous = sd.emptyCells.get(i);
				row = previous.row;
				col = previous.col;
				char previousValue = board[row][col];
				board[row][col] = '.';
				sd.update(row, col, previousValue, true);
			} else {
				board[row][col] = candidate;
				sd.update(row, col, candidate, false);
				if (isOutOfBound(++i, numOfEmptyCells))
					return;
				// Coord next = sd.emptyCells.get(i);
				// row = next.row;
				// col = next.col;
			}
		}
	}

	private boolean isOutOfBound(int i, int range) {
		return i >= 0 && i < range ? false : true;
	}
}