Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #41985

Re: Sudoku

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-26 22:44 -0700
  Re: Sudoku Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2013-03-27 08:58 +0100
    Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-27 20:00 -0700
      Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-28 00:36 -0400
        Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 15:11 -0700
          Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-28 19:28 -0400
            Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 22:07 -0700
            Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 22:07 -0700
          Re: Sudoku Chris Angelico <rosuav@gmail.com> - 2013-03-29 09:45 +1100
            Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-29 14:47 -0700
              Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-29 18:11 -0400
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-30 15:06 -0700
                Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-30 19:15 -0400
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:03 -0700
                Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-31 18:34 -0400
                Re: Sudoku Arnaud Delobelle <arnodel@gmail.com> - 2013-03-31 23:59 +0100
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:03 -0700
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:27 -0700
                Re: Sudoku Chris Angelico <rosuav@gmail.com> - 2013-04-01 09:35 +1100
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 20:58 -0700
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-31 15:27 -0700
                Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-30 15:06 -0700
            Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-29 14:47 -0700
        Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-28 15:11 -0700
  Re: Sudoku Damien Wyart <damien.wyart@free.fr> - 2013-03-27 09:49 +0100
  Re: Sudoku Dave Angel <davea@davea.name> - 2013-03-27 05:38 -0400
  Re: Sudoku Eric Parry <joan4eric@gmail.com> - 2013-03-27 19:49 -0700

csiph-web