SudoCue - Minimum Sudoku-X Collection

The search is continuing 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. There is also a page with Windoku-X puzzles with 9 clues.

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

Puzzles

You can download a zip with the current collection of 552952 puzzles.

If you downloaded one of the earlier collections, discard them. Due to several errors in the canonicalization routine, these files contained several invalid Sudoku-X puzzles, duplicates and non-minlexical entries.

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.

Community search effords

On the New Sudoku Players' Forum there has been a joint effort by Mathimagics, Leren and Ton, expanding my collection of 7193 (after trimming it to 7180) to the amazing number of 552950 unique 12-clue puzzles. I could humbly add 2 more to that list.

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. This dihedral group of transformations does not change the relative position of cells, but only operates on the complete puzzle.
Swapping rows 4 & 6 and columns 4 & 6 gives 2 permutations for each puzzle. It mirrors the middle band and stack, keeping the diagonals intact, albeit in a slightly different order. Permutation of R19C19 with R28C28 and R37C37 gives another order 6, resulting in a total of 8 x 2 x 6 = 96 permutations on the distribution of clues. For each permutation the clues are renumbered in order of appearence and compared with the best result so far, replacing it when better.

Phase 2 (comparing the values separate from the clue positions) is no longer used, because nobody else is using it, even though it offered a slight performance advantage.

Feedback

No code is perfect, and certainly not mine.

• Thanks to Glenn Fowler for his corrections to my original canonicalization method.
• Thanks to Mathimagics for catching the error in this section.
• Thanks to Ryokousha for finding an error in cases where multiple permutations produced the same pattern.

We will continue to look for more 12-clue puzzles, but it is not likely that we ever 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. Any remarks concerning canonicalization, minlexing or attribution are also welcome.