[WelMac] Sudoku mania

[John Crook]

It started innocently enough.  My wife started playing around with 
Sudoku puzzles.  I took a bit of a look at them, but quickly decided 
that they would be boring.  My wife gradually became more adept, moving 
on from easy to medium to hard and then even some "diabolical" puzzles 
although she couldn't always complete the solution for the hardest 
categories.

I said that I couldn't really see the point of these puzzles since they 
only require the repeated application of a few simple logical rules - 
more suited to using a computer rather than a human brain for solving.  
In fact I even went so far as to say that it would be a simple matter 
to write a computer program to solve them.

And then to prove my point, that's what I started to do.  First I had 
to settle on a suitable programming language to use.  Actually, it's a 
very long time since I've done any real programming.  In my past I've 
worked with FORTRAN and PL/I, BASIC and various operations interpreter 
languages.   I've even programmed the early microprocessors in both 
machine code and assembler. More recently I've done a little work in 
Pascal.

But the computing world has changed a great deal since those days.  All 
the same, I thought it wouldn't be too too hard to learn one of the 
modern languages.  What a bewildering array we now have.  I didn't 
really want to spend much money on this exercise, since it was really 
only intended to prove a point - although perhaps I might (re)acquire a 
useful skill in the process.

So I started to look around and see what I already had on my Mac, and 
whether any of it would do the job.  I first tried just using an Excel 
spreadsheet, but found rather quickly that the 'circularity' 
restrictions on spreadsheet cells prevented me from making anything 
other than a sheet that helped a bit in identifying answers for the 
very simplest of Sudoku puzzles - and even then it required manual work 
to enter the found values as the answers for various cells were 
revealed.

I considered using AppleScript but abandoned this idea when I found 
that it didn't seem to possess the capabilities for array variables 
that I felt I needed.

Finally, I settled on VBA (Visual Basic for Applications) since this 
comes included with the Microsoft Office Suite that i already had on my 
computer and it appeared to be quite cable of handling 
multi-dimensional arrays.

The next problem I had was deciding how to start learning the new 
language.  There is an extensive help file system with the program but 
this contains a bewildering mass of information and detail. I couldn't 
tell where to start.  I felt a bit like the apocryphal blind men trying 
to understand what an elephant looked like.  (One had hold of the 
trunk, another its tail, and one had one of the legs.) It was beginning 
to look like it might be a life's work just to understand the language 
before I could start programming to prove my simple point. I decided 
that I needed to get some overall appreciation of the language before I 
could start and then just use the bits I needed, without having to get 
a comprehensive grasp of absolutely everything it could do.

I gave in and decided to sacrifice my pride and spend a little money.  
I bought a book entitled "Absolute Beginner's Guide to VBA" (no prior 
programming experience required).  It sounded like it might have what I 
needed.

Actually the book wasn't too bad.  An evening's reading gave me the 
basics. I guess I cheated a bit.  My prior programming experiences 
would have helped.  I think it would be a a rather steeper learning 
curve for an absolute beginner, but lots of examples helped to quickly 
get the gist of what the language does and how to do it.  One of the 
important things I learned was that you can make "macros" automatically 
by setting the program to "record" a macro while you use the keyboard 
to interact with an MS Office programme such as Excel.  Then you can go 
and look at the resulting code and make any changes you want to make it 
behave in the way you want.

So - a couple of enjoyable evenings were spent figuring out the logic 
to make my program interact with the Sudoku grid, which I entered on an 
Excel spreadsheet.  A little bit more time to get this tested and 
working.

Then the time for the real experiment.  I now had to code those simple 
logical rules that would solve the Sudoku puzzle.  Well first of all i 
decided that perhaps I should try and solve one myself, rather than 
just looking cynically over my wife's shoulder.  I picked a medium 
level one, and actually, it wasn't too bad.  It seemed that only two 
fairly simple logical rules needed to be applied in order to solve one 
of these puzzles - of course proving the point I was trying to make in 
the first place!!!

A couple of days to figure out and program the logic and test it on a 
sample puzzle.  To my joy (and surprise) after a few debugging cycles, 
it actually worked on the sample puzzle that I'd chosen for my previous 
manual exercise on puzzle solution.  A bit slower than I'd expected.  
It took about 3-4 minutes to crank out the completed puzzle.

So far so good - or so I thought.  Let's try another puzzle.  That 
worked too!!!  I was on a roll.  I tried some my wife couldn't solve.  
That was fine too.  OK, now for the real test, let's try some of of 
these diabolical puzzles.

Crash!!!  My wonderful program stopped with the solution only partly 
completed.  Fortunately I had designed it to put all those little 
numbers to show the possibilities in the unsolved cells, just like the 
Sudoku pros use when they're working on the puzzles.  My daughter has 
started as well, so I know all the language ( I don't mean what they 
say when the puzzles don't come out).  I can be an armchair expert, 
without actually have done a puzzle (well OK - only one puzzle).

Well that wasn't too bad.  I managed to figure out a third rule in 
addition to the two, I had programmed into my solver.  That got me by 
in this instance.  (I haven't actually programmed the third rule yet.  
I just used it to solve a single cell and put it back into my program, 
which then completed the solution.)

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!!

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.
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.
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?  (Actually I can usually solve those 
puzzles on a trial-and-error basis by taking a guess at one of the 
unsolved cells and seeing if it comes out - but that is hardly in the 
spirit of the thing - or is it?)

I'm happy to share my solver with anyone who'd like a copy.  (Please 
ask).  But please be aware that this is still a work-in-progress.

Cheers

John