Solving Sudoku using backtracking

Image-1 From left to right (i) sudoku puzzle (ii) answer to puzzle

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 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

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.

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;
}
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;
}
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;
}
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;
}

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.

Data science enthusiast

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store