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.
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.
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:
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.
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.
|© 2005,2007 Ruud||~||Views: 7744|