Solving Sudoku using backtracking

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

Problem

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

Defining constraint definitions

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

Data science enthusiast