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.

4 responses to “Solving sudokus made simple

  1. Pingback: More on sudokus « Keet blog

  2. Pingback: Improbable Research » Blog Archive » 5524751496156892842531225600 on the road to Sudoku

  3. Pingback: 8 years of keetblog | Keet blog