My wife, Jane, is into the Su Doku thing. I'm not. But yesterday I asked myselft, "How long would it take my computer to solve one of those puzzles using brute force." You know, just try every possible combination until one works.

So, retired nerd that I am, I wrote a little program.


Nothing fancy, just a little iterative hack. The only hard thing was making it aware of what a 'failure' was and then making it correctly 'undo' the cells back to the proper place. Anyway, 4 or 5 hrs later I have something running.

So I borrowed her book and enter a couple of problems. (Oh, Yeah, I also had to make a 'puzzle entry routine' and a 'save the puzzle to file' routine and a 'read the puzzles from file' routine. Normal stuff and, again, nothing fancy) The first puzzle I tried was labeled 'Mild' and the computer solved it in less than a second using only 110 iterations. That was not a good representation. So I tried two more.

Difficult puzzle: 6,500 Iterations
Fiendish puzzle: 55,000 Iterations

That's more like it. In this context, an 'iteration' is each entering of a number into a cell.

Then Jane told me about one of the logic rules she uses: "Look for those cells that have only one possible value."
So back to the keyboard I go. I program that logic and the two puzzles attempts look like this:

Difficult puzzle: 219 Iterations
Fiendish puzzle: 2,600 Iterations

Much better.
But then my daughter (Crazy kid that she is, she's also into this stuff. She didn't believe that I'd never even tried one, myself.) tells me about another logic trick: "look for a number that can only go in one cell (kind of the reverse of the first rule)."

So I add that to the program and it looks like this:

Difficult puzzle: 87 Iterations
Fiendish puzzle: 82 Iterations


Pretty amazing, huh? On the hard one, we went from 55,000 to 82 with the application of a little logic.

And with some additional instrumentation of the application I came up with these figures:

	Difficult Puzzle	Fiendish Puzzle
Forward Moves	87	82
Reverse Moves	31	23
Single Option Moves	83	79
Multi Option Moves	4	3
Slice & Dice Hits	369	229
Dead Ends	1	1

I understand there are more hints and tricks. But that's enough to satisfy my curiosity.

Oh, the puzzles and solutions I used were these.
Here's the "difficult" one.


And here's the "Fiendish" one.

(Disregard the yellow cells, they were just marking the 'multiple decision' cells during solutions.)