Solving Sudoku
The last example in this tutorial is coming up with a solution to one of my favorite combinatorial games-- Sudoku-- via backtracking!
Sudoku is a classic example of a problem with constraints, which can be solved via backtracking. It works like magic! To simplify the problem, let's use an easier version of the sudoku game.
We can model the game as an N * N grid, each cell having numbers from 1 .. N.
The rule is not to repeat the same number in a column or row. The initial sudoku board has numbers in some cells, and are empty for the rest. The goal of the game is to fill out the empty cells with numbers from 1 .. N, so that the constraints are satisfied. Let us now look at how backtracking can be used to solve a given Sudoku board.
xxxxxxxxxx21
Routine: solveInput: Sudoku boardRule: No repetition of a number in the same row or columnAssumption: The initial board configuration is according to Sudoku rules​Base case:1. If all empty places are filled return success2. If all combinations are tried and the board is invalid, return false​Recursive case (returns success or failure):1. Choose an empty cell2. For each candidate number i in the range 1..N a. Place the candidate i in the empty cell b. Check if the board is valid with candidate i. If the board is valid, then { i. result = invoke the solve routine on the next empty cell ii. If result is true then stop and return success } else Continue with the next candidate as given in step 23. return failure (no possible combination is possible)OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment