On Sudoku solving

Question

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
       }
     }
   }
 }

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

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!