Backtracking

Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems. [src: Wikipedia ]

Flow

• Find position (row, col) of an unassigned cell
• If there is none, return true (ends)
• For digits from 1 to 9
  • If there is no conflict for digit at row, col
    • assign digit to row, col and recursively try fill in rest of grid
  • If recursion successful, return true
  • Else, remove digit and try another
    • If all digits have been tried and nothing worked, return false

Algorithms