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.
--
http://mail.python.org/mailman/listinfo/python-list
