The New Sudoku Players' Forum

[Mathimagics]

.
In a previous thread (Killing with Flowers) we discussed the problem of finding computationally difficult Killer Sudoku's (with, of course, a unique solution). One obstacle to expanding the list of known cases was the lack of a solver that could test a puzzle for uniqueness of solution in a timely fashion.

Now we have just such a tool in sigh's ISS (Interactive Sudoku Solver).

ISS is web-browser based, so it can't be invoked by a conventional API. sigh kindly provided me with a basic template that can be used to invoke the solver locally, and from this I have extended it into a batch mode facility - given a list of puzzles, it checks each for uniqueness of solution, and tags each valid puzzle with NG, the total number of T&E guesses used by the solver (we will use NG hereafter as a standard metric for comparison purposes).

For example, with given puzzles (from the previous thread):

Code: Select all

S<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O>>^^^>^W^<<^>^^O^<<^T^J^^^>>>^>^>^ML<S<<^^>^<^<<^< # Tarek #41
O<P<<Q<<<^>^KJ<<Q^^K<^<<^^<^^KD9<K<^O^^^6<^K^^>^H<^^^Q^<LK<<>^^O^^<<^P<^^<<<>>^>^ # Wecoc #1A


the script produces:

Code: Select all

S<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O>>^^^>^W^<<^>^^O^<<^T^J^^^>>>^>^>^ML<S<<^^>^<^<<^< #     2654
O<P<<Q<<<^>^KJ<<Q^^K<^<<^^<^^KD9<K<^O^^^6<^K^^>^H<^^^Q^<LK<<>^^O^^<<^P<^^<<<>>^>^ #    39500


We also need a minimality test. For our purposes, a puzzle is non-minimal if any two cage sums can be omitted (given as 0) and the resulting puzzle still has a unique solution.

I have not attempted a script-based minimality tester (yet!) but I do have a function that can use a SAT solver to explore cage-sum redundancy. That function can produce a list of minimal puzzles from a base puzzle, and that list can then be fed into the batch script solver.

Both examples above are non-minimal, as it happens. The hardest (maximum NG) cases found for each puzzle were:

Code: Select all

S<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O>>^^^>^W^<<^>^^O^<<^T^J^^^>>>^>^>^ML<S<<^^>^<^<<^< # tarek #41
0<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O>>^^^>^W^<<^>^^O^<<^T^J^^^>>>^>^>^M0<S<<^^>^<^<<^< #   306918
S<J<<O<<K0^<<^<^>^^<N<<<J^Q^S^0>>^^^>^W^<<^>^^O^<<^T^0^^^>>>^>^>^ML<S<<^^>^<^<<^< #   326311
0<J<<O<<KJ^<<^<^>^^<N<<<J^Q^S^O>>^^^>^W^<<^>^^O^<<^0^J^^^>>>^>^>^ML<S<<^^>^<^<<^< #   358528


Code: Select all

O<P<<Q<<<^>^KJ<<Q^^K<^<<^^<^^KD9<K<^O^^^6<^K^^>^H<^^^Q^<LK<<>^^O^^<<^P<^^<<<>>^>^ # Wecoc #1A
0<P<<Q<<<^>^KJ<<Q^^K<^<<^^<^^KD9<0<^O^^^0<^K^^>^H<^^^Q^<LK<<>^^O^^<<^P<^^<<<>>^>^ #   409550
0<P<<Q<<<^>^KJ<<Q^^K<^<<^^<^^KD9<K<^O^^^6<^K^^>^0<^^^Q^<LK<<>^^O^^<<^0<^^<<<>>^>^ #   444494
0<P<<Q<<<^>^KJ<<Q^^K<^<<^^<^^KD0<0<^O^^^6<^K^^>^H<^^^Q^<LK<<>^^O^^<<^P<^^<<<>>^>^ #   529217


In the next post I will outline the process by which I searched for cases of even "harder" killers ...

[Mathimagics]

.
To find harder Killers, I began by generating layouts using cages of size 5. These seemed to me to be most likely to produce harder Killers.

Using a polyomino-packing function, I generated a list of cage layouts with these properties:

• diagonally symmetric layouts

• 16 cages of size 5, plus a singleton cage as the central grid position

• no cage wholly contained within a row/column/box

• no cage with a 2x2 subsquare (i.e. "twiggy" cages)

With these restrictions, the enumeration found 38,774 distinct layouts.

Having selected a particular layout, the next stage involved finding valid sum combinations that produced valid (unique solution) puzzles, then testing those puzzles with ISS to find their NG rating. To find valid sum combinations I developed a recursive procedure to "explore" the sum settings, using the SAT solver as a local test function.

For any valid sum combination, we can also use the unique solution to relabel the grid in various ways, and test the puzzles obtained by the corresponding set of new sums derived from those grids.

After some days (!) of experimenting, I found this layout which produced several puzzles with very high NG ratings:

Code: Select all

+---+---+---+---+---+---+---+---+---+
|               |               |   |
+   +---+---+---+---+   +---+---+   +
|   |               |   |   |       |
+---+---+---+   +---+---+   +---+   +
|           |   |       |   |   |   |
+   +---+---+---+   +---+   +   +   +
|   |   |           |       |   |   |
+   +   +---+---+---+   +---+   +---+
|   |       |   |   |   |       |   |
+---+   +---+   +---+---+---+   +   +
|   |   |       |           |   |   |
+   +   +   +---+   +---+---+---+   +
|   |   |   |       |   |           |
+   +---+   +---+---+   +---+---+---+
|       |   |   |               |   |
+   +---+---+   +---+---+---+---+   +
|   |               |               |
+---+---+---+---+---+---+---+---+---+


The hardest puzzles found on this layout:

Code: Select all

R<<<M<<<U^M<<<^J>^R<<^S<^R^^P>>^>^^^^^<R5^>^MP^>^V<<^^^^^>^L>>^^<^K>^<<R^>>^<>>>^ #   535830
R<<<M<<<U^M<<<^J>^R<<^S<^R^^O>>^>^^^^^<R6^>^MP^>^V<<^^^^^>^L>>^^<^K>^<<R^>>^<>>>^ #   572004
S<<<K<<<U^N<<<^K>^P<<^U<^P^^O>>^>^^^^^<Q7^>^NL^>^V<<^^^^^>^N>>^^<^O>^<<P^>>^<>>>^ #   586399
R<<<M<<<U^M<<<^J>^R<<^S<^Q^^P>>^>^^^^^<R5^>^NP^>^V<<^^^^^>^L>>^^<^K>^<<R^>>^<>>>^ #   592160
R<<<M<<<U^M<<<^J>^R<<^S<^S^^P>>^>^^^^^<R5^>^LP^>^V<<^^^^^>^L>>^^<^K>^<<R^>>^<>>>^ #   660175
S<<<K<<<U^N<<<^L>^P<<^U<^O^^O>>^>^^^^^<Q7^>^NL^>^V<<^^^^^>^N>>^^<^O>^<<P^>>^<>>>^ #   680734
S<<<K<<<V^N<<<^K>^P<<^U<^P^^O>>^>^^^^^<Q7^>^NL^>^V<<^^^^^>^N>>^^<^O>^<<O^>>^<>>>^ #   721098
S<<<K<<<U^N<<<^K>^P<<^U<^O^^O>>^>^^^^^<Q7^>^NL^>^V<<^^^^^>^N>>^^<^P>^<<P^>>^<>>>^ #   726469
S<<<K<<<U^O<<<^K>^P<<^U<^P^^O>>^>^^^^^<Q7^>^NL^>^U<<^^^^^>^N>>^^<^O>^<<P^>>^<>>>^ #   767364
M<<<R<<<N^N<<<^Q>^N<<^O<^S^^L>>^>^^^^^<T6^>^NR^>^R<<^^^^^>^U>>^^<^N>^<<N^>>^<>>>^ #   770285
S<<<K<<<U^N<<<^K>^P<<^U<^P^^O>>^>^^^^^<Q7^>^NK^>^V<<^^^^^>^O>>^^<^O>^<<P^>>^<>>>^ #   857412
R<<<P<<<S^L<<<^V>^P<<^K<^M^^Q>>^>^^^^^<R7^>^ML^>^L<<^^^^^>^Q>>^^<^U>^<<Q^>>^<>>>^ #   916001
M<<<R<<<N^O<<<^Q>^N<<^O<^S^^L>>^>^^^^^<T6^>^NR^>^Q<<^^^^^>^U>>^^<^N>^<<N^>>^<>>>^ #  1045880
M<<<T<<<O^O<<<^R>^N<<^N<^N^^N>>^>^^^^^<U7^>^OO^>^M<<^^^^^>^U>>^^<^R>^<<N^>>^<>>>^ #  1556843