## July 2008 riddle

UPDATE (1 August): So far, there have been no complete solutions for the July riddle. The riddle will therefore run one extra month, but with the modification that solvers are now asked to tackle either of the two parts, rather than both, to qualify. A new August riddle will be posted, as usual, in parallel to this one.

If you've been on earth in the past few years, you've heard about Sudoku, the game that took over newspaper riddle columns and is all about completing a 9-by-9 board so that every row, every column and every sector (3x3 tile) will contain each of the 1-9 digits exactly once.

If you ask any serious Sudoku player, you will hear that the most important thing in the game is that one should never guess. The solution must always be reached by logical reasoning. I tried to formalize what one means by said reasoning.

Let A be a set of positions, let B be a second set, disjoint to A, and let C be their union. Furthermore, for any set X and any digit i let Ximin be the minimum number of i's that could possibly inhabit the positions in the set, let Ximax be the maximum number, and let |X| be the number of positions in the set.

The following inequalities must hold:

0≤XiminXimax≤|X|
Aimin+BiminCiminAimin+BimaxCimaxAimax+Bimax
Either ΣiXimin<|X|<ΣiXimax or ΣiXimin=|X|=ΣiXimax

To these inequalities, the "extra information" we are given can be added. The Sudoku constraints regarding rows, columns and sectors (henceforth known as the "basic constraints") can be formulated as

For each i, Ximin=Ximax=1

for any X that is the set of positions composing a row, a column or a sector. The extra constraints derived from our partial knowledge of the board are of the same form, but where X is a set containing a single position and i is the digit given in this position on the board.

The idea is that every time additional information is given, this narrows the gap between our "minimum" estimate and our "maximum" estimate. We can now go over the inequalities above one by one. In each inequality, we can substitute the latest min/max information into the inequality, and we can see that the gap between minimum and maximum for another variable can thus be narrowed.

More concretely, the inequalities can be translated into the following rules:

1. If A contains i then so does C.
2. If C does not contain i then neither does A.
3. If C contains one i and so does A, B contains no i.
4. If C contains i and A does not, then B contains i.
5. If there are |X| elements known to be in X then X contains no other elements.
6. If all elements except |X| of them are known not to appear in X, the remaining elements are the members of X.
Repeating this systematically, we can reach a point in which for each set the minimum equals the maximum, and, in particular, for all sets of size 1 we know which i appeared in them.

This is at least my point of view regarding what we mean by "reasoning" in Sudoku. The provided Python program demonstrates how this can be done. Almost the only modifications it does over the scheme described above is that it doesn't examine each equation every time a variable is updated, but only those equations containing variables that have been updated, and that it considers only sets that are subsets of the basic (row/column/sector) constraints. (Examining sets that are not subsets of the basic constraints can easily be shown not to matter.) Here is a sample session with the program:

```\$ cat > board.txt
8  3   9
24   1
1   7 3
9   3
7   4   6
6   8
4 5   9
5   42
9   1  8

\$ cat board.txt | python sudoku.py
```

The program runs and outputs the filled-in board. Due to the slowness of the program (a solution takes roughly 15 minutes. Sorry.), it also outputs intermediate board positions, as variables are resolved. In Python interactive mode, the program also knows to report traces of its reasoning via the "explain" method, as demonstrated below:

```\$ python
>>> from sudoku import *
>>> f=open("board.txt")
>>> f.close()
>>> p=sudoku()
>>> p.solve(board,False)
876315492
532489617
149276385
425967831
718543926
963128754
384752169
651894273
297631548

>>> p.explain("I4","4")
The position list contains 4 .
This was discovered by elimination, after finding that it cannot contain 1 2 3 5
6 7 8 and 9.
>>> p.explain("I4","2")
The position list does not contain 2 .
This is true because the list I7 and I9 has it.
>>> p.explain("G7 G9 H7 I7 I9","2")
The position list contains 2 .
This is true because the list G7 G8 G9 H7 H8 I7 I8 and I9 has it, but the list G
8 H8 and I8 alone does not.
>>> p.explain("G8 H8 I8","2")
The position list does not contain 2 .
This is true because the list C8 has it.
>>>
```

The "explain" interface allows querying over position sets of any size. Position names are given chess-like notation. The second parameter to the "solve" method is verbosity.

Consider now the following definitions:

• A legal Sudoku problem is a partially filled Sudoku board that can only be completed in a single manner, while maintaining the basic Sudoku constraints.
• A reasonable Sudoku problem is a legal Sudoku problem that can be resolved by use of the rules shown above alone. (Effectively, a problem is reasonable iff "sudoku.py" can solve it.)
Finally, note that even though Sudoku is normally played on a 9x9 board, we can easily define Extended Sudoku as a game played on an N2xN2 board, using N2 symbols, each repeating exactly once in every row, column and NxN tile. Regarding generalized Sudoku, one can speak of complexity classes for the amount of time required for a solving algorithm. The program "Sudoku.py", for example, is clearly hyper-exponential in N, as it needs to resolve O(2N^2) sets in order to complete.

This month's riddle is composed of two questions:

1. Describe a polynomial time algorithm that will solve any reasonable extended Sudoku board (or prove none exists).
2. Find a (non-extended) legal Sudoku problem that is not reasonable (or prove none exists).
To appear on the list of solvers, solve both parts.

### List of solvers:

#### Both parts:

Itsik Horovitz (1 August 20:34)
Hongcheng Zhu (3 August 15:31)
Bojan Bašić (16 August 20:29)
Oded Margalit (29 August 21:42)

#### Part 2 only:

Elegant solutions can be submitted to the puzzlemaster at riddles brand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!