# 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

## Defining constraint definitions

`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

## More from Shankar Y Bhavani

Data science enthusiast