Solving sudokus made simple

Sudokus seem to be the latest puzzle excitement in several countries, published daily in various (online) newspapers. My brother puts them in excel, which saves him from some adding up and he has added encouraging “OK” and “you have won!” etc., but it doesn’t make solving the Sudokus any easier. There are cleverer ways to do it. Knowing the ‘easy’ way maybe like cheating, but on the other hand, it also gives insight in the thought processes you go through when trying to solve them (apart from the sense of frustration an joy of course).

Alas, Helmut Simonis used Constraint Programming to get to the solution quickly [1]. How did he do it? Well, first you assume you want to solve the puzzle using constraint programming, so then you a) formulate the problem, b) make a model and write the program in e.g. ECLiPSe, c) add some constraints, a propagation scheme, and d) test with Sudokus from the The Times, Daily Telegraph, Minimum Sudoku, and from Puzzler. Here is how it goes.

A. To formulate the problem, we first define what a filled-in Sudoku square is. In plain English, the Sudoku square consists of 81 cells in a 9 by 9 square, where each cell contains some number that ranges from 1 to 9 and the cells in each row and each column as well as each of the nine 3 by 3 major blocks have different numbers throughout. To be pedantic, and swapping 3 for ‘n’: “A Sudoku square of order n consists of n4 variables formed into an n2 x n2 grid with values from 1 to n2 such that the entries in each row, each column and in each of the n2 major n x n blocks are alldifferent.”. The real Sudoku problem can then be defined as that it “consists of a partial assignment of the variables in a Sudoku square. The objective is to find a completion of the assignment which extends the partial assignment and satisfies the constraints.”. Then you want Sudokus that have only one solution, that don’t have redundant information, and should be solved without guessing. 

B. The model was written in ECLiPSe and the relevant code is in the article [1].

C. To strengthen the deduction by combining several of the original constraints (to make things more manageable for the program by linking up the various constraints), so-called redundant constraints are added. These involve how the row and column interact, how rows and blocks interact, how the three affect each other, and then “shaving”. The latter, shaving, is a constraint programming technique whereby the whole set of constraints is taken and variables tested; i.e. assign a number to a cell, if it fails then remove the lot from the domain. This helps to throw out inconsistent values before you even start for real. There are a bunch of “propagation schemes” that deal with the alldifferent constraint, that is, how to make sure that in each row, column, and block each of the numbers 1-9 occur only once.

D. The testing phase. With the previous points in place, you run the program. It could solve quite well all Sudokus except for the Daily Telegraph’s “tough” and “diabolical” Sudokus. To solve those, apparently we’d need more powerful reasoning for that, or some searching, or at least the above-mentioned shaving technique.There are two other curious things that came afore during testing. First, most of the published puzzles contain more than 10 redundant hints that you can do without with and still have that there is one unique solution. Second, it appeared that the grading of the difficulty of the Sudokus actually corresponds quite well with the real difficulty of solving the puzzle.

You can read more details and find links to further information and (Sudoku) puzzles in Simonis’ article. For those of you who are in or around Bolzano, your next chance to go to a seminar about constraint programming & solving puzzles is the 8th of June 2006, by Rosella Gennari.

[1] Simonis, H. Sudoku as a Constraint Problem. In: Proceedings of the 4th International Workshop on Modelling and Reformulating Constraint Satisfaction Problems. Hnich, B. Prosser, P., Smith, B. (ed.). 2005. pp. 13–27.

About these ads

8 responses to this post.

  1. [...] a year ago I wrote about solving sudokus with constraint programming, which some readers still found a bit too cumbersome. Santos-Garcia and Palomino had a go with it [...]

    Reply

  2. [...] use a count of a mere 6,670,903,752,021,072,963,960 — for solutions for a 9 x 9 grid (see [3,7] for an informal summary of [2,6]) — which has wikipedia as referenced source [4], that [...]

    Reply

  3. Hello,

    I thought you’d enjoy taking a look at the following paper:

    http://koala.ilog.fr/wiki/pub/Main/HassanAitKaci/lifesudoku.pdf

    It was fun writing. I hope it is as much fun reading … Comments welcome.

    Cheers,

    -hak

    Reply

  4. […] The 8-year anniversary swooshed by a few days ago, but, actually it’s really only completing today, as the first blog post with real content was published on April 18, 2006, about solving sudokus with constraint programming. […]

    Reply

  5. Admiring the dedication you put into your site and in depth information you offer.
    It’s awesome to come across a blog every once in a while that isn’t
    the same old rehashed information. Excellent read!
    I’ve saved your site and I’m adding your RSS feeds to my Google account.

    Reply

  6. Your style is so unique compared to other folks I’ve read stuff from.
    Thanks for posting when you’ve got the opportunity, Guess I’ll just
    bookmark this page.

    Reply

  7. Hello friends, its impressive article on the topic of tutoringand completely defined, keep
    it up all the time.

    Reply

  8. I read this article completely about the difference of most up-to-date
    and previous technologies, it’s amazing article.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 37 other followers

%d bloggers like this: