help on sudoku solving

Question

Can someone please help me understand this solution http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku#Example_of_a_brute_force_Sudoku_solver_.28in_C.29

Answer 1

It's a simple brute force solver. It starts from the top left, working left to right line by line, trying to place each possible number into each square, and continuing by using a recursive call. On failure it backtracks and tries a different alternative.

The function called safe determines whether it is currently legal to place the value n in a certain cell, by checking which values have already been placed in the row, column and box.

It's one of the simplest (and slowest) ways to solve a Sudoku.

Answer 2

The best way to understand the code is to use debugger and see step by step.

Answer 3

The most confusing thing was that I expected the algorithm to fill the sudoku matrix with correct values on finish, but instead it just prints the values and then backtracks to the beginning as the value of t variable is always written back to the grid (maybe algorithm even manages to find another solution).

In order to have the grid filled when the algorithm finishes one could make the solve function return true/false and then decide whether to trace back based on the result of inner calls.

Answer 4

There are a lot of ways to solve Sudoku (don't know if you're interested in it in general). It is fundamentally a Constraint Satisfaction Problem, and you can apply your favorite consistency checking techniques (e.g. AC3) to propagate constraints and prune obviously fruitless paths much earlier. Your variables are each square, the domain each variable can take is the integers 1 through 9. Constraints are AllDiff on various subsets of the cells.

You can also formulate it as an Integer Linear Programming problem and just let your favorite ILP engine (e.g. lp_solve) solve it!