On Sudoku solving

问题:

Can someone please help me understand this solution:

 Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
 Fill in some empty grid with the known values
 Make an original copy of the array
 Start from top left grid (nx = 0, ny = 0), check if grid is empty
 if (grid is empty) {
   assign the empty grid with values (i)
   if (no numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
     fill in the number
   if (numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
     discard (i) and repick other values (i++)
 }
 else {
   while (nx < 9) {
     Proceed to next row grid(nx++, ny)
     if (nx equals 9) {
       reset nx = 1
       proceed to next column grid(nx,ny++)
       if (ny equals 9) {
         print solution
       }
     }
   }
 }

回答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.

回答2:

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!

回答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.