Soduku Solver

LeetCode Q 37 - Soduku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

• Each of the digits 1-9 must occur exactly once in each row.
• Each of the digits 1-9 must occur exactly once in each column.
• Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

Solution

Method: Backtracking

1. Our Choice: place 1 - 9 in an empty cell.
2. Our Constraints: placement cann’t break rules.
3. Our Goal: fill the board.

This is a NP-complete problem.

Code:

public void solveSudoku(char[][] board) {
	solve(board);
}

private boolean solve(char[][] board) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] != '.') continue;

			for (int num = 1; num <= 9; num++) {
				board[i][j] = (char) (num + '0'); // choose
				if (isValid(board, i, j) && solve(board)) // explore
					return true;
				board[i][j]; // unchose
			}
			return false;
		}
	}
	return true;
}

private boolean isValid (char[][] board, int x, int y) {
	Set<Character> seen = HashSet<>();
	for (int i = 0; i < 9; i++) {
		if (board[i][y] == '.') continue;
		if (!seen.add(board[i][y])) return false;
	}

	seen = HashSet<>();
	for (int i = 0; i < 9; i++) {
		if (board[x][i] == '.') continue;
		if (!seen.add(board[x][i])) return false;
	}

	seen = HashSet<>();
	int row = x / 3, col = y / 3;
	for (int i = row * 3; i < row * 3 + 3; i++) { 
		for (int j = col * 3; j < col * 3 + 3; j++) {
			if (board[x][i] == '.') continue;
			if (!seen.add(board[x][i])) return false;
		}
	}

	return true;
}