Sudoku

November 20, 2006 | Comments Off

On our flights to Maui I was doing the usual in-flight magazine reading, and since the flights were sufficiently long, I got through the magazine not long after we started the second (longer) leg. This is usually the point at which I start doing the crossword, which I attempted but crosswords aren’t my forte; I don’t have enough practice with them to get their hints (tip: if the clue ends with a question mark, it’s probably remarkably obtuse). So I figured I’d try this whole sudoku thing I keep hearing about.

There were three puzzles, effectively: easy, medium, difficult. Easy had already been attempted, so I figured I’d start with medium. I really butchered it pretty badly before I got the hang of how they get solved and that’s around the time I regretted only bringing a pen. So armed with newfound knowledge I spent a good part of the rest of the flight making my first informed attempt with the difficult puzzle, and I had it maybe half way filled.

I realized as I was doing the puzzle that the committed mistakes weren’t logic errors but accounting mistakes. I’d overlooked that this cell could or couldn’t have this number, and that the vast majority of the puzzle solving was record keeping the number sets as opposed to logical noodling. I made a mental note that I’d write a program to help with the tedious bit.

On the flight back I happened to get the American Airlines spanish-language magazine (no puzzle sections, unfortunately) which entertained me for a while but soon my attentions turned to sudoku. Leigha was asleep and I was stuck in the middle so I got my contraband laptop out of where I had cleverly smuggled it in the seat-back pocket and began.

My first thought was to do it in MS Excel, I thought I remembered Excel having union/intersection functions, but apparently there weren’t any, which left me in a pickle. My next choice would have been to hack something together in perl but I didn’t have an environment. So I resolved to cram it into Excel as best I could. Effectively I ended up translating all of the simple set logic into hundreds of cells. I ended up with an input sudoku grid (fill in the cells here) and an output grid (these are the numbers this cell could have). When a cell can only have 1 number, it turns red. When you fill that red number into the input grid, it turns blue and recomputes (no VisualBasic was used/harmed/cursed in the making of this sheet).

Now the sheet doesn’t do any real logic for you – just tracks the sets and which numbers are legal in which cells, this doesn’t autosolve for you because the clever puzzle makers expect you can do set math without error (which apparently, I can’t). Then you get to the logic portion of the puzzle and that’s where the real fun lives. Now the sheet could do some of the easier logic, but I’ve lost interest in impleneting the one I thought would be easiest; i.e., if this cell is the only one that can hold this number, the number must go here. I think I’ll save that for my next flight.

As a side note: I’ve always had the impression that crossword puzzles would be trivial to write (computationally). All you need is an obscure wordset and a grid and the computer should be able to figure it out. Then all you do is write clues to the requisite level of obscurity. Sudoku on the other hand seems like a trickier puzzle to write. I imagine one would start with a full grid (computer can help here), and then start removing numbers and create the mental leaps the player must make. The downside of sudoku (and, incidentally, the reason I think it will not last long) is that there’s likely to be a limited set of logic patterns to use, and once the player knows those (and has a handy record keeping tool!) it might get old. Of course there might not be any applicable logic and the player would have to resort to trial and error.

I’ve put the Sudoku Solver up for download. It is released under GPL. Additionally, no macros were used so if you get prompted for macro priveldges decline.


No Comments yet

Sorry, the comment form is closed at this time.