Brute force sudoku cracker

[David Durkee]

Hi Bas,

I came across Soduko puzzles recently too and had the same reaction:  
why waste my time solving the things when it would be much more fun  
to write a Python program to do so?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: soduko.py
Type: text/x-python-script
Size: 8270 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20050917/69d6b6c4/attachment.bin>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: puzzle1.txt
URL: <http://mail.python.org/pipermail/python-list/attachments/20050917/69d6b6c4/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: puzzle2.txt
URL: <http://mail.python.org/pipermail/python-list/attachments/20050917/69d6b6c4/attachment-0001.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: puzzle3.txt
URL: <http://mail.python.org/pipermail/python-list/attachments/20050917/69d6b6c4/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: puzzle4.txt
URL: <http://mail.python.org/pipermail/python-list/attachments/20050917/69d6b6c4/attachment-0003.txt>
-------------- next part --------------

I've enclosed my script and four puzzle files. The puzzle files are  
text files containing nine lines of text, and containing nine digits  
or spaces. Your puzzle 3 is the one in the file puzzle4.txt.  
Interestingly, the file puzzle3.txt is the first one I ran across  
that my earlier version couldn't solve. You must pass in the puzzle  
file path as a single parameter to the script.

My script originally used two strategies, which I called solve-by- 
needed and solve-by-possible. I found that neither strategy used by  
itself completed as much of the difficult puzzles as alternating  
between both strategies. However, even both together didn't  
completely solve my puzzle 3 (or yours). I found I wasn't even able  
to solve it myself unless I narrowed one space down to two  
possibilities and took a guess. Of course, sometimes I would guess  
wrong and have to keep track of where I was to be able to go back to  
that state and make the other guess. Obviously a computer program can  
do this more easily than I can, so I incorporated that as a third,  
last resort strategy. This, so far, has always worked, and I can't  
imagine it not working on a solvable puzzle. It seems like cheating,  
though. I wrote it recursively, as making one guess can lead to  
another situation where the puzzle is still solvable but strategies  
one and two get stuck. I've never seen it recurse more than twice  
with a real puzzle. With a really gross test I call "ones test", a  
puzzle in which only nine ones are filled in (which obviously has  
many possible solutions), it recursed very deeply and still succeeded  
in producing a possible solution.

David

On Sep 16, 2005, at 3:45 PM, Bas wrote:

> I came across some of these online sudoku games and thought after
> playing a game or two that I'd better waste my time writing a solver
> than play the game itself any longer. I managed to write a pretty dumb
> brute force solver that can at least solve the easy cases pretty fast.
>