DC Examiner Classic Sudoku

Last weekend, I spent waaaay too much time on the DC Examiner's Classic Sudoku puzzle (6 star difficulty). But that was a week ago, and I've been doing a lot of puzzles. I can't be sure, but I think the programming project might also be causing me to have some improvement as well.

I blew through the 5 star Sudoku Pacific rather easily. Then, I turned my attention to the Sudoku Classic puzzle. At about 30 minutes in, I was pretty sure it was another diabolical puzzle. I inked in the numbers I was certain about, and switched to a pencil. I had to choose between a 6 and an 8 at Row 4, Column 5-- wound up choosing the 6 and discovered about 6 minutes later that path resulted in a conflict. At that point, I had to erase everything from the past six minutes worth of work. That was disheartening. I chose the "8 path" at that point, and was rolling along until an hour and 18 minutes had passed-- and that's when I hit a brick wall.

I've never heard of such a thing as a "double diabolical" puzzle, but I found myself once again in the position of being unable to eliminate any of the remaining possibilities on the grid and having to pick one of two pairs. I suppose it is possible that I overlooked something, but in every row and column the number of empty squares and the number of possible values were equal. At this point, I was so mentally exhausted, I stopped for lunch and took a break to watch an episode of "My Name Is Earl" on the DVR.

Then, I came back and took a new stab at the puzzle. Once again, I couldn't find any way to break the chain of possible values down further-- so I inked in the numbers I'd picked once again (no turning back now, right!?) and choose a path to explore. Fortunately, it turned out to be the correct one. Total time spent on the puzzle: 1 hour and 48 minutes.

Now, I need to get some aspirin and lie down. ;)

Sudoku Solver Program Idea

If I keep writing about Sudoku all the time, people will think I'm obsessed. Or boring. I'm not sure which is worse. Obsessed people have some possibility of being freakishly intriguing to a small audience that shares the same interest/hobby. Boring is just . . . well, boring.

I digress.

Tonight, I find myself preoccupied with the idea of creating a computer program that solves Sudoku puzzles-- including diabolicals. I haven't tested every single solver program in existence, obviously, but the ones I have seen don't appear to solve diabolical Sudoku puzzles. At first, this made sense-- the program is applying the various solving techniques (lone number, hidden pairs, etc.) and takes the puzzle as far as it can go with those techniques. Once the techniques stop producing results, the process has no choice but to stop.

But computers aren't humans, and vice versa.

Instead of trying to make the computer mimic human solving techniques and processes, it makes sense to capitalize on the unique strength of the computer's raw computational power. There are 81 cells in a typical Sudoku puzzle, with 9 possible variables in each cell-- that's 9 to the 81st power (or, um . . . 1.96627050476e+77 for those playing along at home). I know that seems like a lot, but with advances in processor speeds, distributed clients, and a smart approach, it isn't completely impossible. Right? Also, don't forget that the values of some of the squares are given at the start (28 given clues in yesterday's diabolical puzzle), so it's more like 9 to the 53 power (aka 3.75710212614e+50).

It's basically a multi-dimensional array, 9 by 9. It helps to think of a series of car tripometers when trying to visualize this-- except each tripometer has nine places, and they are stacked one right above the other. You increment the value of the last cell, and then you perform a series of 18 checksums-- one for each row, and one for each column. If the checksums each add up to 45, then you have a valid sudoku solution. If not, then you know there's at least one number that is wrong, you increment the number again and start over. Humans don't have the speed or patience to pull off such maneuvers-- but computers are fantastic at this sort of thing.

You could do it as a series of 81 nested for loops as well, I suppose, but that'd be crass and ugly. This reminds me of a program I wrote years ago that generated letter combinations for telephone numbers to help people find "vanity" numbers for their phones. Same concept, except you'd be running the process on nine digit numbers instead of seven.

If you really wanted to make it fast, I think you could create a "dictionary" of valid Sudoku puzzles-- in other words, run the program and let it generate all the possible valid combinations of numbers for all possible complete Sudoku puzzles (much like password cracking programs use dictionaries to assist their attacks). Then, all you'd need to do is run a match against the given clues and filter out all the solutions that don't match the values and positions of those clues, and-- voila! -- you have your solution. Of course, storing an array of that size (in RAM or hard drive space) might be problematic.

There must be something wrong in one of my assumptions. It can't possibly be *that* easy, or someone else would have already done it. The total number of possibilities (with 28 provided clues) multiplied by 18 checksum operations is 6.76278382705e+51. Of course, you wouldn't carry out all 18 checksums for every possible combination-- you'd stop running checksums as soon as the first one didn't total 45.

What language would you choose to write something like this in? Jeez, almost every programming language I know is web-oriented these days. That's certainly not too practical for this sort of operation. Maybe it's time I dusted off those old C programming skills and see if I can pull this off.

If anyone's interested in taking a shot at this with me, drop me a line.

DC Examiner's Diabolical Sudoku Classic Puzzle

Our local newspaper, the DC Examiner, recently began running two Sudoku puzzles each day-- Sudoku Classic and Sudoku Pacific. Generally speaking, the Monday puzzles are easy and the difficulty level progresses through the week. By the time you get to the weekend edition, you are looking at maximum skill level puzzles. I know my Sudoku solving techniques are incomplete, so I've been drilling myself with these puzzles to try to force myself to improve.

I could be mistaken, but I think the folks in charge of the Examiner's "Games!" page decided to throw us a curve ball this weekend by featuring a "diabolical" puzzle for the Sudoku Classic (shown below). It's marked with 6 out of 6 stars, and about two-thirds of the way through working the puzzle, you reach a point where it becomes impossible to eliminate any more possibilities.



You don't see many diabolical Sudoku puzzles in mainstream newspapers these days. (It tends to upset the so-called Sudoku purists who insist that all puzzles must be solved by logic alone and should never involve any guesswork.) There is a technique called "Ariadne's thread", which I have not mastered, that might address such situations-- but let's be honest here, it amounts to picking a cell with only two possible values, choosing one of those values and solving forwards from there until you either encounter a conflict or solve the puzzle. If you do find a conflict, you erase your way "backwards" to the point before you picked that value, and then you select the other option and progress forwards. Using a photo copier or different colored pencils makes this process much easier.