Problem

Solve a well-posed sudoku puzzle.

What

Sudoku is a popular game that many of you are familiar with. The main idea of the game is to fill a grid with only the numbers from 1 to 9, while ensuring that each row and each column as well as each sub-grid of 9 elements does not contain duplicate numbers.

Examples

Example 1:

Input: board =[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Here is the solved sudoku:

Solution

Sudoku can be solved using multiple algorithms based on Neural Networks and Genetic Algorithms by doing exhaustive searches in the solution space. However, here we are focusing on solving Sudoku using backtracking algorithm.

Method 1 - Backtracking

At each empty cell, we can fill in either of [1, 2, ... , 9], after filling in the values, we have to check if it is a good number or we have to backtrack.

Let’s try using backtracking:

Can We Construct a Partial Solution?

Yes, we can fill in some portions of the board.

Can We Verify if the Partial Solution is Invalid?

Yes, we can check that the board is valid so far if there are no rows, columns, or squares that contain the same digit.

Can We Verify if the Solution is Complete?

Yes, the solution is complete when the board has been filled up. Let’s try to solve it using our template. We’ll try filling each empty cell one by one, and backtrack once we hit an invalid state.

Code

Java
With Set
class Solution {

	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 (char k = '1'; k <= '9'; k++) {
					board[i][j] = k;

					if (isValid(board, i, j) && solve(board)) {
						return true;
					}

					board[i][j] = '.'; // backtrack
				}

				return false;
			}
		}

		return true;
	}

	private boolean isValid(char[][] board, int i, int j) {
		HashSet<Character> set = new HashSet<>();

		for (int k = 0; k < 9; k++) {
			if (set.contains(board[i][k]))
				return false;

			if (board[i][k] != '.') {
				set.add(board[i][k]);
			}
		}

		set.clear();

		for (int k = 0; k < 9; k++) {
			if (set.contains(board[k][j]))
				return false;

			if (board[k][j] != '.') {
				set.add(board[k][j]);
			}
		}

		set.clear();

		int x = i / 3 * 3;
		int y = j / 3 * 3;

		for (int m = x; m < x + 3; m++) {
			for (int n = y; n < y + 3; n++) {
				if (set.contains(board[x][y]))
					return false;

				if (board[x][y] != '.') {
					set.add(board[x][y]);
				}
			}
		}

		return true;
	}
}
Without Set

Before setting the number in board, we can check if it already exists in ith row, jth column or nth block:

class Solution {

	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 (char k = '1'; k <= '9'; k++) {
					if (isValid(board, i, j, k)) {
						board[i][j] = k;

						if (solve(board)) {
							return true;
						}

						board[i][j] = '.'; // backtrack
					}

				}

				return false;
			}
		}

		return true;
	}

	private boolean isValid(char[][] board, int i, int j, char ch) {
		for (int k = 0; k < 9; k++) {
			//check row
			if (board[k][j] == ch) {
				return false;
			}
			//check column
			if (board[i][k] == ch) {
				return false;
			}
			//check 3*3 block
			if (board[3 * (i / 3) + k / 3][3 * (j / 3) + k % 3] == ch) {
				return false;
			}
		}

		return true;

	}
}

Complexity

  • ⏰ Time complexity: O(9^n), where n is number of blank cells.
  • 🧺 Space complexity: O(n) using recursive stack.

The recursion tree in above method will branch into 9 paths, and reduces the number of blank cells by 1.

The number of limit of blank cells n is m*m where m is the size of grid, aka 9x9 in this case. The recurrence equation can be written as

T(n) = 9*T(n-1) + O(1)

Hence O(9^n)