SudoCue

SudoCue - Minimum Windoku-X Collection

 

The program I wrote to find Sudoku-X puzzles with the minimum number of 12 (probably) clues has been adapted to broaden the search to other variants, such as Windoku with a current 11 clues minimum and Windoku-X with a current 9 clues minimum.
This page will keep you informed about the progress of the Windoku-X search and you can download collections with essentially unique Windoku-X puzzles in their minimal form, so far all of them with only 9 clues.

A Windoku-X starting with 5 clueless boxes

This Windoku-X starts with a series of 51 empty cells. That's 5 empty boxes!
It has only 9 clues and a unique solution.
My solver was unable to solve it with the implemented techniques.

Puzzles

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

Search method

I started with some 20000 Windoku-X puzzles from my puzzle generator with 15 or fewer 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, the first 9 clue results quickly appeared. To my surprise, this collection keeps growing by replacing any of the 9 clues with a random other clue. Unlike Sudoku-X and Windoku, this collection is still growing on its own and requires no fresh input. This gives me hope that we may even find an 8 clue puzzle someday.

Canonicalization method

Because of the many constraints, Windoku-X puzzles have far fewer permutations than other Sudoku variants. 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.
No rows or columns can be swapped, neither can any bands or stacks.
The algorithm picks the permutation where the clues are in the rightmost position when presented as a string of 81 numbers, using 0 for each empty cell, 1 for each clue. 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.

© 2005-2021, Ruud ~ Sitemap ~ Contact ~ Privacy policy ~ Valid HTML 4.01 Transitional Valid CSS [Valid RSS] Views: 170