Puzzle generation algorithm

1. Puzzle Creation Rules

   This follows the rules used by Nikoli, whose Sudoku puzzles are published in the Asahi Shimbun morning edition (Tue–Fri). The rules are:

   • When the puzzle is solved, the solution must be unique.
   • The initially opened cells must be rotationally symmetric.
   
   

   Fig. 2

2. Steps of puzzle creation (Nikoli's method)

   Nikoli's website provides a video showing how to create puzzles. According to the explanation, you first decide which cells to open, then choose numbers to place so that a complete solution can be formed.

   
   

   Fig. 3

   The key step in the above figure is ②. You place numbers into the orange cells, and as you proceed you fill in numbers in other cells that can be logically determined. The video spends more than 30 minutes explaining this. The explanation is clear, and after watching it I thought, "I might be able to make puzzles this way." I actually tried, but always failed near the end, when no more numbers could be placed. Nikoli refers to this situation as being "stuck."

3. Steps of puzzle creation (this tool's method)

   I created a tool that generates puzzles using the opposite approach to Nikoli's method.

   I also considered making an interactive tool that follows Nikoli's method, but I abandoned the idea because I anticipated the logic would become quite complex.

   In this tool, the process starts by creating a completely filled grid. A completed Sudoku grid is defined as follows:

   Each row (9), each column (9), and each 3×3 block (9) must contain the numbers 1 through 9 exactly once.

   1. Based on this definition, I designed an algorithm to fill the entire grid using random numbers (The figure above step ①). For the recursive logic in generating the solution, I referred to Sudoku Example Generation . Many thanks for this reference.

   2. The following explanation is based on Fig. 4. Numbers such as ① and ② refer to "step 1" and "step 2."

      Except for the center block specified in "Pattern Selection," the tool randomly chooses pairs of symmetric cells to blank out. See step ③.

      Each time new blanks are added, the tool checks whether the original solution ① can still be reproduced. If the puzzle becomes unsolvable at some point, the last blanks are undone, and other cells are blanked instead (feedback).

      For example, if the target number of opens is set to 26:

      If blanking fails when narrowing down to 30, the filled grid ① is discarded and a new one is generated, then the process continues from ②. See step ⑤.

      If narrowing down succeeds to 28 but fails at 26, the grid ① is kept and the process continues. See step ⑥.

      The creation of the solution (a fully filled 9×9 set of cells) is based on random numbers. While checking the narrowing process for making blanks, I began to feel that some solutions are easier to narrow down than others. When the target is 26 and narrowing reaches 28, I thought that by continuing to use that solution, it should eventually yield 26. Since applying this logic, I have been able to generate puzzles with 23 and 24 open cells, so I don't think this reasoning is entirely wrong.

      The count for “Number of Repeats” begins during trials after the final form is fixed. If a puzzle cannot be created even after exceeding the number of repeats, a message box will appear, displaying the minimum number that could be created. See step ⑧.

   
   
   
   

   Fig. 4