SudoCue - Minimum Sudoku-X Collection

The search is on for the Sudoku-X with the minimum number of clues. Since November 2005, the lowest number was 13 with only two available examples. Now that the hunt for minimum vanilla Sudokus is done by many volunteers, I decided to test these methods of optimization on some Sudoku variants. With Sudoku-X, I soon found thousands of puzzles with 13 clues, which yielded several puzzles with 12 clues. I assembled a collection of unique Sudoku-X puzzles with 12 clues, which you can download from this page.

This Sudoku-X starts with a series of 44 empty cells.
It has only 12 clues and a unique solution.

Puzzles

You can download the current collection of 7193 puzzles.

If you downloaded the earlier file with 3316 puzzles, throw them away. Due to an error in the canonicalization routine, this file contained several invalid Sudoku-X puzzles.

Search method

I started with all Sudoku-X puzzles in my collection with 17 or fewer clues and added the two existing puzzles with 13 clues. With this collection, I performed the following steps:

• Remove each of the existing clues in turn, and place digits 1 through 9 one by one in each empty cell, skipping the cell just cleared.
• Check the validity of each of the resulting puzzles and all valid puzzles to the collection
• Canonicalize the collection and remove any duplicates
• Remove the clues for each puzzle one by one and when any of them have a unique solution, remove the original and add the new puzzle(s) with 1 clue less
• When sufficient puzzles with N-1 clues have been collected, remove all puzzles with N or more clues
• Repeat these steps until no new puzzles can be added

Using this method, a small base of less than 200 puzzles yielded more than a thousand puzzles with 12 clues.

I'm constantly expanding the collection by generating small batches of random Sudoku-X puzzles with 16 or fewer clues, which are then processed the same way as the original set. Some of these sets result in a large number of additions, others only yield a few new 12's. Since there are only few duplicates, I expect the number of 12-clue Sudoku-X puzzles to be very large and the chances to find an 11-clue Sudoku-X are promising.

Canonicalization method

Because of the diagonal constraints, Sudoku-X puzzles have far fewer permutations than vanilla Sudoku. Using reflection and rotation gives 8 equivalent puzzles. These transformations do not change the relative position of cells, but only operate on the complete puzzle. Swapping rows 4 & 6 and/or columns 4 & 6 gives 4 permutations for each puzzle. Permutation of R19C19 with R28C28 and R37C37 gives another order 6, resulting in a total of 8 x 4 x 6 = 192 permutations on the distribution of clues. (thanks to Glenn Fowler for his corrections to my original method) My canonicalization algorithm picks the permutation where the clues are in the rightmost position when presented as a string of 81 numbers. If multiple permutations have the same distribution, they are both tested in phase 2.

In phase 2, the digits are relabeled in order of appearance on the string of 81 numbers. When multiple permutations in phase 1 were pattern-equivalent, their relabeled clues are compared from left to right and the lowest value is chosen as the canonical form. The same canonicalization method is used in SudoCue.

I will continue to look for more 12-clue puzzles, with the ultimate goal to find an 11-clue Sudoku-X. If you like to contribute any 12-clue Sudoku-X puzzles that you have found, I will gladly add them to the collection.