My family has been decimated by the Sudoku bug. I’m actually physically tired of making the “Hey, the year 2005 called and they want their game back” jokes all the time. I’m not sure why is this happening now, but nevertheless everyone keeps solving the damn things. For added humor, my dad keeps forgetting the name of the game and keeps referring to it as seppuku. Whether I want it or not that damn puzzle has entered my household and is not going away anytime soon. Because of this I started looking at he puzzle more closely as an interesting problem to be cracked.
A while ago I mentioned an effective Sudoku solving algorithm – one that you can use with your pen and paper puzzle. For the sake of completeness, let me recount it here:
- Start by writing numbers 1-9 in each empty cell of the puzzle (or get the nifty template with pre-filled numbers)
- Pick one of the given (seed) numbers and eliminate it from the row, column and quadrant it is in (ie. cross it out from the 1-9 lists in these cells)
- If you are lucky, few cells may end up having only one number on the list that was not crossed out – that’s the number that belongs in that cell. Take that number and eliminate it in a row, column and quadrant as above
- If you can’t find a singleton number scan each crow, column and quadrant for a unique non repeating number (ie. one that appears only in a single cell in that row, column or quadrant. If you find one, that’s your number – put it in the cell where it appears and eliminate it from the row, column and quadrant
I believe that you can solve most of the easy, medium and hard sudokus this way. However, now that I actually did some digging, there seems to be a subset configurations in the “evil” range which actually requires trial and error strategies and can’t be solved by simply sticking to the algorithm above. Which of course doesn’t mean the puzzle is not solvable.
In fact, if you look at sudoku really hard it really boils down to the good old graph coloring problem. A standard 9×9 Sudoku grid translates to a graph with 81 vertices. Each vertex has exactly 20 edges connecting it to 20 neighboring vertices (8 more in the row, 8 more in the column and 4 more in the quadrant) and the chromatic number is 9. The bad news is that graph coloring is NP-hard. The good news is that sudoku’s don’t really scale upwards that much. So you can use an algorithm that performs acceptably with sudoku sized graphs (9 colors, 81 vertices, 1620 edges between them) and stick with it.
The fact that sudoku is a book case graph problem not surprising. A lion share of real life problems can be solved using nothing more but graph theory. So here is a word of advice for you younger whipper-snappers out there. Do use the Algorithms class to sleep off your drunken debaucheries – especially not on the day when they are covering Graphs. But don’t take just my word for it, listen to Steve Yegge’s recent rant:
Graphs are, like, really really important. More than you think. Even if you already think they’re important, it’s probably more than you think.
Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it’s about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can’t think of a way to solve it using graphs before moving on to other solution types. This tip is important!
Big question: how many real world graph problems have I encountered at my at my job since I got my degree? I’ll give you three guesses.
The sad truth is that I haven’t touched these things since my algorithms class. Part of it is the nature of my work – which involves a lot of sysadmin stuff, in addition to hacking my PHP+MySQL monster into submission. The problems I face on the daily basis can mostly be solved in polynomial time and usually revolve around storing and fetching data from a database.
This state of things is regrettable but not unusual – a lot of people are in the same boat. Nevertheless, we are getting rusty and these graph problems are important, if for nothing else than for impressing interviewers when looking for another job.
Which tells me I need to dig out my Algorithms book and knock out a Sudoku solver. But which language should I use? I’m thinking Ruby just to get more feel for this language. :)
[tags]sudoku, graph, graph coloring, np-hard, ruby[/tags]