Sudoku Solver

How Does a Backtracking Algorithm Work?

In any backtracking algorithm, the algorithm seeks a path to a feasible solution that includes some intermediate checkpoints. If the checkpoints do not lead to a viable solution, the problem can return to the checkpoints and take another path to find a solution.

ALGORITHM (SUDOKU)

  1. Find an unfilled cell (i,j) in grid
  2. If all the cells are filled then A valid sudoku is obtained hence return true
  3. For each num in 1 to 9
    • If the cell (i,j) can be filled with num then fill it with num temporarily to check
    • If sudokuSolver(grid) is true then return true
    • If the cell (i,j) can't be filled with num the mark it as unfilled to trigger backtracking
  4. If none of the numbers from 1 to 9 can be filled in cell (i,j) then return false as there is no solution for this sudoku