A bit of fun - a Sudoku Solver

wxPython Users
1

Hi all

Let me state up front that I did not write the Solver program itself. It is
a Python program written by David Eppstein, a professor of Computer Science
at the University of Califoria, Irvine. To quote a post from Tim Roberts a
while back, from which I found out about this program, "More than just
solving the puzzles, his script actually prints out the individual steps
that lead to the solution, one by one, in readable English. I've used it
several times just to get a hint at the next step in a solution. It can
also create new puzzles."

I was chatting about Sudoku to a friend the other day, and he said he was
sure that some puzzles have no solution. I told him that I had a program
that would solve any valid puzzle, and he was eager for a copy. Although the
Python program is brilliant, it only has a command line interface, and you
have to type in the grid in a long string. I thought it would be fun to
write a wxPython front-end for it. Here is my attempt.

If you place sudoku_solver.py and sudoku.zip in the same directory, it
should just work. I have tested it on Windows Server 2003, Python 2.5,
wxPython 2.8.9.1, and on Fedora 10, Python 2.6.1, wxPython 2.8.9.1.

My next task is to package it using Gui2exe, to make it easy to install on
my friend's computer. I thought I would post what I have done so far, to see
if I get any feedback. It is just a toy, but it would be nice to get it
working as smoothly as possible.

If you don't have a puzzle handy, there is one included in the program, but
commented out. Just uncomment the lines, and run it.

Any comments will be appreciated.

Frank Millman

P.S. The attachments are about 36k - I hope I am not exceeding the
acceptable limit.

sudoku_solver.py (10.6 KB)

sudoku.zip (25.4 KB)

2

Hello,

···

2009/3/18 Frank Millman frank@chagford.com

If you don’t have a puzzle handy, there is one included in the program, but
commented out. Just uncomment the lines, and run it.

Any comments will be appreciated.

Looks pretty nice. I started a small sudoku program last spring when I had to do some airport hopping. I thought that the ui was interesting so I made the code available at googlecode (http://code.google.com/p/wxsudoku/). I haven’t looked at it since last year but there might be something useful in it for you to take or adapt.

All the bundled puzzles unfortunatly are puzzles for testing solvers so they are not very fun (nor possible) to play yourself, but it supports loading puzzles from pickles that can be generated ( I think I included the script for generating the pickles), but I don’t remember much as I haven’t looked at it since the initial draft about year ago.

Cody

3

(Caution -- off topic)

Frank Millman wrote:

I was chatting about Sudoku to a friend the other day, and he said he was
sure that some puzzles have no solution.

That depends entirely on your definitions. There is a surprising amount
of research on sudoku puzzles. In part, that's because sudokus are a an
interesting cross between number theory and topology. Solving a sudoku
turns out to be equivalent to coloring a map in topology, and there is
still a lot of research going in those areas.

You can place 9 copies of the digits 1 through 9 in a 9x9 matrix in many
ways (5 x 10^27), but most of those ways violate the sudoku rules, by
having duplicates in the rows, columns or cells. Once you discard all
of those, you are left with 6x10^21 arrangements. It should be clear
that any puzzle that maps to one of those can be solved (meaning that
"there is at least one solution").

If by "solution" you mean "only one unique solution", then that is a
more interesting question. The question then becomes, how many numbers
can you remove and still have a unique solution? The answer is, no one
knows. If a grid contains only 7 of the 9 digits, it has been proven
that the puzzle has at least two solutions.

One theorist has created a solvable 9x9 puzzle with only 17 givens. In
fact, he has found 35,000 such puzzles. No one has yet found a solvable
puzzle with only 16 givens, although no one has proven it can't be done,
either.

Here's another interesting sudoku tidbit. It turns out that every
solved sudoku grid can be derived from every other solved sudoku grid by
(1) shuffling the rows of blocks, (2) shuffling the columns of blocks,
(3) shuffling the rows within one row of blocks, (4) shuffling the
columns within one column of blocks, and (5) shuffling the grid 90 degrees.

I told him that I had a program
that would solve any valid puzzle, and he was eager for a copy. Although the
Python program is brilliant, it only has a command line interface, and you
have to type in the grid in a long string.

Actually, his app ignores whitespace, so you can enter the grid as a
natural 9x9 matrix.

···

--
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

4

Cody Precord wrote:

2009/3/18 Frank Millman <frank@chagford.com <mailto:frank@chagford.com>>
    Any comments will be appreciated.

Looks pretty nice. I started a small sudoku program last spring when I had to do some airport hopping.

How many of us have done this??

Enclosed is my version:

This one does not provide puzzles, nor does it help you solve them.

However, it does display them, and will highlight the appropriate row, column,
or box if there is an error in the puzzle at any time, as you add numbers, etc.

What's unique about this one is the use of numpy arrays. Numpy arrays have two
properties that make them handy for this problem:

1) n-d arrays (in this case 2-d)
2) slices as views on the data

The whole puzzle is a 9X 9 array
   each box is a 3X3 sub-array
   each row is a length 9 array
   each column is a length 9 array

these are share the same memory

-Chris

sudoku-chb.py (10.7 KB)

···

--
Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR&R (206) 526-6959 voice
7600 Sand Point Way NE (206) 526-6329 fax
Seattle, WA 98115 (206) 526-6317 main reception

Chris.Barker@noaa.gov