# 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 solutionFAILURE - Value returned when constraints are not satisfiedDomain(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.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.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.length) {        return true;    }    if (col == grid.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.