English/Japanese

Notice

It is reported that this sudoku puzzle is solved easily by hand. Perhaps, the definition of the difficulty is not appropriate.

Notice (Mar. 13)

We have revised the definition of the difficulty.
This puzzle cannot be solved only with basic techniques, hopefully.
But this is not the world hardest, of course.

Notice (Mar. 13) 9 PM

We have revised the definition of the difficulty again.
Is it difficult?

Notice (Mar. 22)

We obtained another one.

We made a program to create difficult Sudoku puzzles, and succeeded to create (hopefully) the world hardest one, as of March 2013.

The above puzzle is created by the super computer (SGI Altix ICE 8400EX) at ISSP, the University of Tokyo. Its depth is 10, normal width is 183530, and average width is about 100571 (the definitions of these properties are given later). It requires several ten thousands recursive backtracking to solve. I think it is impossible to solve it by hands.

To our best knowledge, the world hardest Sudoku puzzle is created by Dr. Arto Inkala who is a Finnish mathematician. He created a difficult puzzle in 2010 (Inkala2010). Later, he created a more difficult one in 2012 (Inkala2012).

(c) Arto Inkala www.aisudoku.com

Sudoku puzzles created by Dr. Inkala. (a) The puzzle made in 2010 (Inkala2010), which depth is 5, normal width is 173, and average width 179, respectively. (b) The puzzle made in 2012 (Inkala2012), which depth is 8, normal width is 3599, and average width = 2257, respectively.

Our goal was to create a puzzle which is more difficult than Inkala2012.

It is not trivial, as Dr. Inkala mentioned, to define the difficulty of a Sudoku puzzle. Generally, difficulty of puzzles depends on a method to solve them. Therefore, we first define a method to solve Sudoku puzzles. While there are many kinds of techniques to solve Sudoku puzzles, we adopt the following two techniques, pencil marks and recursive backtracking.

Pencil Marks: Pick up an empty cell. Check all the numbers in the row, column, and subblock to which the cell belongs. Then list up all numbers which are still possible in the empty cell. These numbers are called pencil marks. If there is a cell which has only one pencil mark, then the mark is the value of the cell. Repeat this procedure until all empty cells have two or more pencil marks.

Recursive Backtracking: Pick up the cell which has the smallest number of pencil marks. Then chose one of the pencil marks and assume that it is the value of the cell, and continue to solve the problem recursively. If the assumed value does not lead to the complete solution, then chose another value of the pencil marks.

The procedure to solve a sudoku puzzle is, first determine numbers with pencil marks as possible, then pick up the cell with the smallest number of pencil marks and assume that one of them is a solution and repeat this procedure recursively until one finds a solution.

We do not include pencil makrs part in difficulty since computational costs for it are cheap. We define difficulty using a tree structure created by recursive backtracking.

The originally-provided puzzle is the root node of the tree. Then pick up the cell with the smallest number of pencil marks, and create children for each candidate. If each child node is not solved by pencil marks and does not face inconsistency, then create child nodes recursively. A leaf node, which is a node without any children, is a solution of the puzzle, or inconsistent configuration. We define two properties, depth and width. Depth is the distance between the root node to the node of the solution. Width is a number of nodes in the tree. We define the difficulty of a puzzle by width of the tree associated with the puzzle.

There can be more than two cells which share the number of pencil makrs
and the number is the smallest in the Sudoku grid.
Then the values of width and depth depend on which cell is chosen for
recursive backtracking.
Therefore, we define the shortest path as depth, i.e.,
the least number of recursive calls to solve a puzzle.
We define two kinds of width, normal width and average width.
**Normal Width**
If there are two or more candidates of cells, then choose a cell
in the top-left order. Then the value of the width is deterministic.
With this definition, the normal width depends on the orientation of a puzzle.
**Average Width**
If there are two or more candidates of cells, then choose a cell randomly.
We define the expectation value of the width as the average width,
and adopt it as the difficulty of the puzzle.
We average them for 100 independent samples to calculate the average width.

The average width of Inkala2012 is 2257, while that of Inkala2010 is 179. Therefore, Inkala2012 is more than 10 times more difficult than Inkala2010 in our definition.

We define 81 Ising spins and associate a spin with each cell. If a spin is up, then the number in the cell associated with the spin is left. Otherwise, the number is removed. Then we define a Ising spin-glass like Hamiltonian as follows.

where s_i is a state of i-th spin, J is the interaction energy, U is the internal energy, and h is the external field, respectively. We create difficult puzzle by minimizing the energy define by the Hamiltonian. We first create a complete Sudoku grid randomly, which is a base of the puzzle. Then we remove numbers from the grid to create a puzzle. While our goal is to find the puzzle with a large value of the width, we find that it is difficulty to find difficult puzzle only by the search in the width-first order. Therefore, we first perform simulations in the depth-first order, and then we switch to those in the width-first order.

We performed Markov Chain Monte Calro simulations to update spin configurations. We also adopted the Replica Exchange Monte Calro method to search difficult problems efficiently.

We performed simulations on SGI Altix ICE8400EX at the Institute for Solid State Physics, the University of Tokyo, and created a difficult puzzle shown at the top of this page. Its depth is 10 and average width is 100571, which is more than 40 times more difficult than Inkala2012 in our definition.

We define a Ising spin-glass like Hamiltonian which describe the difficulty of Sudoku puzzles. We adopt the replica-exchange Monte Carlo method to minimize the energy of the model and we succeed to create a puzzle which is the world hardest in our definition, to our bestknowledge. Of course, the definition of the difficulty of Sudoku puzzle is not unique. Therefore, a different definition of the difficulty leads to a different result. But the method presented here is quite general, so it is easy to apply our method when we adopt different definition of the difficulty.

Author: Hiroshi Watanabe