Solving Sudoku using backtracking
Problem
Sudoku is a logic based number placement puzzle. The term sudoku is originated from Japanese, where Su means ‘Number’ and Doku means ‘Single’. The objective of the problem is to fill 9x9 grid with the following rules
- Every row should be filled with numbers 1 to 9 only once.
- Every column should be filled with numbers 1 to 9 only once.
- Every 3x3 sub-grid should be filled with numbers 1 to 9 only once.
Backtracking
Wiki definition: Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.
Backtracking is one of the most used technique for solving problems such as puzzles, crosswords, sudoku etc.; This uses recursion to incrementally build solutions and remove the solutions that doesn’t meet constraints set by the problem definition.
Pseudocode
c - Candidate solution
FAILURE - Value returned when constraints are not satisfied
Domain(var) - Set of all possible values that can be accommodated at the given position.accept(v) - returns true if the candidate satisfies all constraints.
complete(v) - returns true if the solution is final.
next(v) - returns next unassigned value of given candidate.function backtrack(c)
return c if (complete(c) == true)
var <- next(c)
while val in Domain(var):
if consistent(c U {val}) then :
result <- backtrack(c U {val})
return result if (result != FAILURE)
return FAILURE
Solution
The naive solution using backtracking is to assign all possible values between 1 to 9 one by one in each unassigned square and check for all constraints till correct board configuration is found.
Step-1: Find an empty location in the grid.
Step-2: Fill it with any number from 1 to 9.
Step-3: Verify the constraints set for row, column and 3x3 sub-grid (defined above)
Step-4: If the current number is can fit in location goto step-1 else goto step-2.
Defining constraint definitions
Defining row constraint : all values in row has to be unique
public static boolean canFitInRow(int[][] grid,int row, int col,int val) {
for (int idx=0; idx<grid[0].length;++idx) {
if (grid[row][idx] == val) {
return false;
}
}
return true;
}Defining column constraint : all values in column has to be unique
public static boolean canFitInColumn(int[][] grid, int row, int col, int val) {
for (int idx=0; idx<grid[0].length;++idx) {
if (grid[idx][col] == val) {
return false;
}
}
return true;
}Defining sub-grid constraint : all values in sub-grid has to be unique. In order to get the first cell of the square (sub-grid), we take modulus of the row, and then, we subtract this number with row number in order to get the top right row value of the square. We can do the same in order to get the most top right column value of the required square.
public static boolean canFitInSubGrid(int[][] grid, int row, int col, int val) {
int startRow = row - row%3, startCol = col-col%3;
for (int row_idx =0; row_idx<3;++row_idx) {
for (int col_idx =0; col_idx<3;++col_idx) {
if (grid[startRow+row_idx][startCol+col_idx] == val) {
return false;
}
}
}
return true;
}Defining backtracking trigger method: In order to solve the sudoku, we need to find each unassigned square and try options from 1 to 9.
public static boolean solveSudoku(int[][] grid, int row, int col) {
if (row == grid.length-1 && col == grid[0].length) {
return true;
}
if (col == grid[0].length) {
++row;
col = 0;
}
if (grid[row][col] != 0) {
return solveSudoku(grid, row, col+1);
}
for (int num = 1; num < 10;++num) {
if (validGrid(grid, row, col, num)) {
grid[row][col] = num;
boolean canSolveSudoku = solveSudoku(grid, row, col+1);
if (canSolveSudoku) {
return true;
}
grid[row][col] = 0;
}
}
return false;
}Complete code can be found here.
Complexity analysis
Complexity of the above implementation is O(9n²), where n being the dimensions of the sudoku grid. Value 9 in the complexity signifies, for each unassigned square we have 9 possible values. Value n² signifies we traverse grid atleast once.
Resources
Thanks for reading this article.
