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

Groups > comp.lang.python > #42075

Re: Sudoku

Show all headers | View raw

On Wednesday, March 27, 2013 6:28:01 PM UTC+10:30, Ulrich Eckhardt wrote:
> 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

Thank you for your explanation.
I noticed that in this particular puzzle when it ran out of candidates in a particular cycle, it then changed the last entry to the next one in line in the previous cycle. But I cannot find any code to do this.
I was hoping to understand the logic so that I could re-write it in VBA for excel which would enable any puzzle to be entered directly.
Your comments are a big help especially the double negative aspect.
Eric.

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