The Sudoku Infection

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:

  1. Start by writing numbers 1-9 in each empty cell of the puzzle (or get the nifty template with pre-filled numbers)
  2. 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)
  3. 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
  4. 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]

This entry was posted in programming. Bookmark the permalink.



7 Responses to The Sudoku Infection

  1. Matt` UNITED KINGDOM Mozilla Firefox Windows Terminalist says:

    I used to use the “pencil in tiny little numbers then work by elimination” method. One thing that might need to be considered that you didn’t cover up top is the effect of pairs/triples.

    If 2 boxes in one column have the same 2 numbers left (and only those 2), then that pair of numbers must be in that pair of boxes, and so those numbers can be eliminated from the rest of the line.

    You can also remove all other numbers from a box if its one of a pair and there’s nowhere else for the 2 numbers to go, which may mean one other box is left as the only possibility for one of the numbers you removed.

    Some of the harder ones will require you to make a choice somewhere and follow it through, while being prepared to go back to that point if it turns out that was wrong, some will have multiple dead ends and possible trails to follow.. I don’t like those ones, feels too fuzzy and not logic-y enough. The Times’ puzzles are all pure logic though

    Reply  |  Quote
  2. Dax UNITED STATES Opera Windows says:

    I actually ran into a “graph problem” in my work once. I boiled the problem I was trying to solve down to an issue of topological sorting. Funny thing was that I didn’t need to implement a graph to accomplish it.

    As far as Sudoku goes, I’m not much of a fan. I prefer to solve Kakuro puzzles.

    Reply  |  Quote
  3. Luke Maciak UNITED STATES Mozilla Firefox Ubuntu Linux Terminalist says:

    @Matt` – Ah, good suggestion. I didn’t think of that. Thanks – this actually improves the human based algorithm a bit. :)

    Reply  |  Quote
  4. Luke Maciak UNITED STATES Mozilla Firefox Windows Terminalist says:

    @Dax – yeah, these things do come up. They never did for me though.

    Also, I didn’t know about Kakuro. It’s like a crossword puzzle… Only without words. Heh!

    Reply  |  Quote
  5. ths GERMANY Mozilla Firefox Windows Terminalist says:

    german c’t magazine had a very nice article in issue 20/2006, and the author discussed the mathematics required and the backtracking algorithm he used quite nicely. The article came with a nice sudoku software for playing and solving, written in C#, and it requires .net 2.0+.

    Reply  |  Quote
  6. Matt` UNITED KINGDOM Mozilla Firefox Windows Terminalist says:

    I’m sure I had some other trick to bust out when the going got really tough… can’t remember what it was though.

    Reply  |  Quote
  7. Shannon ISRAEL Mozilla Firefox Windows says:

    Tanks for the pencil tip, I’m not a huge fan of sudoku but I do it sometimes and it might help make my life easier.

    Reply  |  Quote

Leave a Reply

Your email address will not be published. Required fields are marked *