[WelMac] Sudoku mania

[David Empson]

At 4:52 PM +1300 5/3/2006, John Crook wrote:

[Big story about writing a Sudoku solver snipped, though I enjoyed it 
very much.]

>All right, now the real test.  Let's get some of the real toughies.
>
>I found that my program does solve many of these without complaint, but
>frustratingly, some it doesn't.  What's more, my third rule doesn't
>crack them either.  Two more rules later and I've got one or two more
>cells solved, but still the puzzle(s) won't come out.
>
>I'm stuck now.  At the moment I can't see any more "simple rules" that
>will crack these puzzles.  Maybe there's more to this Sudoku thing than
>than I thought.  Perhaps I'm in danger of getting addicted after all!!

There are a few "Diabolical" Sudoku puzzles which cannot be solved by 
simple logic. It is necessary to guess which number goes in a 
particular cell, then try to complete it. If a conflict is found, 
unwind back to the point of the guess and try another number. In some 
cases, I've had to do two or three of these guess sequences, though I 
expect this could have been reduced if I'd picked a better candidate 
for the cell in which I made my first guess.

I have a Sudoku puzzle program on my PDA/cellphone (Palm Treo 600), 
and I've kept most of the puzzles published in the Dominion Post on 
there. I don't usually see the paper on a Saturday so I've missed 
most of the diabolical ones. The program can generate puzzles (no 
setting for diffulty) or you can enter the numbers from another 
source. It can also solve them or offer hints, but I don't need that. 
:-)

The first time I did a Diabolical puzzle it took me about three hours 
to solve (on paper). It is now rare for them to take me more than 
half an hour. I find the rating system used by the DomPost somewhat 
arbitrary, and I suspect it is more related to the complexity of the 
logic required to solve the puzzles rather than the time taken. I 
have solved some Gentle puzzles in about four and a half minutes, but 
others have taken longer than ten minutes. Moderates are typically 
five to fifteen minutes, Tough is six to thirty minutes, Diabolical 
is ten to thirty minutes.

I usually find Moderate ones the easiest (Gentle tends to just be a 
plod) and the Tough and Diabolical ones more interesting.

>I have some questions both about programming in VBA and about Sudoku.
>
>1.   Does VBA actually compile the program?  It seems very slow for a
>compiled program.

Don't know. Standalone Visual Basic does compile the program, but VBA 
might be compiled to an intermediate form which is then interpreted 
(quite common with scripting languages).

>2.   How can I get VBA to show intermediate results while it is
>working?  At the moment, my program "goes away" and doesn't display
>anything happening on my spreadsheet until it has finished the
>computations.  I would really like to watch it filling in the cells
>progressively.

I'm not familiar with the language so can't suggest anything 
specific. In other scripting languages there is often a statement 
which will display data in a dialog box, or refresh the display, or 
pause execution while an intermediate result is displayed.

>3.   Are there any Sudoku-meisters out there who would like to look at
>the partially completed puzzles that I cannot solve, and tell me what
>other logical rules I might use?

Fire away. I should at least be able to determine whether I would be 
able to find a solution by logic or can't do it without guesswork.

I haven't attempted to formally describe the rules I use to solve 
Sudoku puzzles, and haven't seen any standardised terminology which 
would allow mutual understanding of such rules, but then again I 
haven't gone looking for any.

Here are my rules. The first three are usually sufficient to solve 
Gentle and Moderate puzzles.

My first step is to look at all of the instances of a particular 
digit in the puzzle and see whethere there are any other 3x3 squares 
into which that digit can be placed immediately, allowing for other 
instances of the same digit in intersecting rows and columns, 
sometimes requiring two or three nested intersections. I tend to go 
through all of the digits in order of frequency before trying other 
rules. (This could probably be turned around to look at missing 
numbers in each 3x3 square, but I prefer to work the other way.)

My second step is to look at each row and column and identify the 
missing digits, then see if any of those digits can only go in one 
possible position, concentrating on the rows and columns with the 
fewest gaps first. At this step I start noting which numbers can 
appear in particular cells.

My third step (done at the same time as the second step) is to look 
for any "pairs" in a row, column or 3x3 square, i.e. unsolved cells 
which can be either of two possible digits, and there is another cell 
in the same row, column or 3x3 square which has the same two possible 
digits. If so, this allows those digits to be eliminated as 
possibilities in every other cell in the same row, column or 3x3 
square, which may identify further pairs or individual cells in which 
only one possibility remains.

My fourth step is to look for patterns in the placement of possible 
numbers in the unsolved cells within 3x9 blocks. Consider the case 
where no instance of a particular number has yet been placed in a 
horizontal 3x9 block, but all the cells which might hold that number 
have been identified. If the number can only be placed in either of 
two rows for one 3x3 square, and either of the same two rows in a 
second 3x3 square, then it must be located on the third row in the 
third 3x3 square, allowing any potential instances on the other two 
rows within the third square to be eliminated. This can be repeated 
vertically, and there are some minor variations.

I think that covers it. After using each rule I tend to repeat the 
earlier ones in case more numbers pop out.

-- 
David Empson
dempson at actrix.gen.nz
Snail mail: P.O. Box 27-103, Wellington, New Zealand