Problem:
Write a program to solve a Sudoku puzzle.
Sudoku is a popular puzzle game. The goal of Sudoku is to fill a 9×9 grid with numbers so that each row, column and 3×3 section contain all of the digits between 1 and 9.
Solution:
This is a typical backtracking problem. For current cell, we try numbers from 1 to 9, if a number is valid, then we recursively try the rest of the cells. If the current number is invalid or the rest of the cells can not be filled correctly, we try the next number.
class Solution {
public static boolean sudoku(int[][] board, int n) {
int N = board.length;
if(n > N * N - 1)
return true;
int i = n/N;
int j = n%N;
if(board[i][j] > 0) { //skip none-empty cell
return sudoku(board, n+1);
} else {
for(int k = 1; k <= N; k++) {
board[i][j] = k;
if(isValid(board, i, j) && sudoku(board, n+1)) {
return true;
}
}
board[i][j] = -1; //put it back
return false;
}
}
private static boolean isValid(int[][] board, int row, int col) {
for(int i = 0; i < row; i++) { //cells above
if(board[i][col] == board[row][col])
return false;
}
for(int j = 0; j < col; j++) { //cells left
if(board[row][j] == board[row][col])
return false;
}
for(int i = 3 * (row/3); i < 3 * (row/3) + 3; i++) {
for(int j = 3 * (col/3); j < 3 * (col/3) + 3; j++) {
if(board[i][j] > 0 && !(i == row && j == col) && board[i][j] == board[row][col]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[][] board = new int[9][9];
board[2][2] = 4;
printBoard(board);
System.out.println(sudoku(board, 0));
printBoard(board);
}
private static void printBoard(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(String.format("%3d", board[i][j]));
}
System.out.println();
}
}
}
public static boolean sudoku(int[][] board, int n) {
int N = board.length;
if(n > N * N - 1)
return true;
int i = n/N;
int j = n%N;
if(board[i][j] > 0) { //skip none-empty cell
return sudoku(board, n+1);
} else {
for(int k = 1; k <= N; k++) {
board[i][j] = k;
if(isValid(board, i, j) && sudoku(board, n+1)) {
return true;
}
}
board[i][j] = -1; //put it back
return false;
}
}
private static boolean isValid(int[][] board, int row, int col) {
for(int i = 0; i < row; i++) { //cells above
if(board[i][col] == board[row][col])
return false;
}
for(int j = 0; j < col; j++) { //cells left
if(board[row][j] == board[row][col])
return false;
}
for(int i = 3 * (row/3); i < 3 * (row/3) + 3; i++) {
for(int j = 3 * (col/3); j < 3 * (col/3) + 3; j++) {
if(board[i][j] > 0 && !(i == row && j == col) && board[i][j] == board[row][col]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[][] board = new int[9][9];
board[2][2] = 4;
printBoard(board);
System.out.println(sudoku(board, 0));
printBoard(board);
}
private static void printBoard(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(String.format("%3d", board[i][j]));
}
System.out.println();
}
}
}
Since the board size is fixed, there is no big O with N notation.
The time complexity has upper boundary (9^81)*27. The number 9^81 is because for each cell, we can have 9 options, there are 81 cells. For each option, check validity took 27 compares. We check at most 9 same row cells, 9 same column cells and 9 same cubic cells. It is upper bound because not all 81 cells are empty and we only have to compare the cells above and left of the current cell and we compare few cells for those invalid options.
The space complexity is 81, the size of board.
We can trade space for time. If we can keep updating all the allowed numbers for the 81 cells at each step, we don't have to try all the 9 numbers. We only have to try 9! numbers for the 9 cells in a row. There are 9 rows, so the total time complexity will be (9!)^9*81, which is substantially faster than the simple backtrack code above. The space complexity will be more than 81*10, besides associate a value to each cell, we have to associate an extra set to each cell for the allowed numbers. Set's object overhead and references will make 10 fold memory increase an under-estimate.
The time complexity has upper boundary (9^81)*27. The number 9^81 is because for each cell, we can have 9 options, there are 81 cells. For each option, check validity took 27 compares. We check at most 9 same row cells, 9 same column cells and 9 same cubic cells. It is upper bound because not all 81 cells are empty and we only have to compare the cells above and left of the current cell and we compare few cells for those invalid options.
The space complexity is 81, the size of board.
We can trade space for time. If we can keep updating all the allowed numbers for the 81 cells at each step, we don't have to try all the 9 numbers. We only have to try 9! numbers for the 9 cells in a row. There are 9 rows, so the total time complexity will be (9!)^9*81, which is substantially faster than the simple backtrack code above. The space complexity will be more than 81*10, besides associate a value to each cell, we have to associate an extra set to each cell for the allowed numbers. Set's object overhead and references will make 10 fold memory increase an under-estimate.
