Sudoku

[Ulrich Eckhardt]

Am 27.03.2013 06:44, schrieb Eric Parry:
> I downloaded the following program from somewhere using a link from
> Wikipedia and inserted the “most difficult Sudoku puzzle ever” string
> into it and ran it. It worked fine and solved the puzzle in about 4
> seconds. However I cannot understand how it works.


In simple terms, it is using a depth-first search and backtracking. If 
you really want to understand this, get a book on algorithms and graphs 
(or locate an online source). I can try to give you an idea though.


 > It seems to go backwards and forwards at random. Can anyone explain
 > how it works in simple terms?

I think your interpretation of what it does is wrong or at least flawed. 
It does try different combinations, but some don't lead to a solution. 
In that case, it goes back to a previous solution and tries the next one.


I'll try to document the program to make it easier to understand...

> def same_row(i,j): return (i/9 == j/9)
> def same_col(i,j): return (i-j) % 9 == 0
> def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
>
> def r(a):
      # find an empty cell
      # If no empty cells are found, we have a solution that we print
      # and then terminate.
>    i = a.find('0')
>    if i == -1:
>      print a
>      exit(a)

      # find excluded numbers
      # Some numbers are blocked because they are already used in
      # the current column, row or block. This means they can't
      # possibly be used for the current empty cell.
>    excluded_numbers = set()
>    for j in range(81):
>      if same_row(i,j) or same_col(i,j) or same_block(i,j):
>        excluded_numbers.add(a[j])

      # create possible solutions
      # Try all possibly numbers for the current empty cell in turn.
      # With the resulting modifications to the sodoku, use
      # recursion to find a full solution.
>    for m in '123456789':
>      if m not in excluded_numbers:
>        # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
>        r(a[:i]+m+a[i+1:])

      # no solution found
      # If we come here, there was no solution for the input data.
      # We return to the caller (should be the recursion above),
      # which will try a different solution instead.
      return


Note:

  * The program is not ideal. It makes sense to find the cell with the 
least amount of possible numbers you could fill in, i.e. the most 
restricted cell. This is called "pruning" and should be explained in any 
good book, too.

  * The style is a bit confusing. Instead of the excluded numbers, use a 
set with the possible numbers (starting with 1-9) and then remove those 
that are excluded. Then, iterate over the remaining elements with "for m 
in possible_numbers". This double negation and also using exit() in the 
middle isn't really nice.


Good luck!

Uli