Using your Head is Permitted

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 Xⁱ_min be the minimum number of i's that could possibly inhabit the positions in the set, let Xⁱ_max be the maximum number, and let |X| be the number of positions in the set.

The following inequalities must hold:

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 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.

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")
>>> board=f.read()
>>> 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.)

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).

List of solvers:

Both parts:

Part 1 only:

Part 2 only: