Creating Minimum / Irreducible Sudocus

Question

Sudoku's puzzle is minimal (also called irreducible) if it has a unique solution, but deleting any number will give a puzzle with several solutions. In other words, each digit is necessary to determine a solution.

I have a basic algorithm for generating minimal Sudocus:

• Create a completed puzzle.
• Visit each cell in random order. For each cell visited:
  • Pre-delete your digit
  • Solve the puzzle twice using the recursive backtracking algorithm. One solver tries the numbers 1-9 in the direct order, the other in the reverse order. In a sense, solvers cross a search tree containing all possible configurations, but from opposite ends. This means that two solutions will match if the puzzle has a unique solution .
  • If the puzzle has a unique solution, delete the number permanently; otherwise return it.

This method is guaranteed to create a minimal puzzle, but it is rather slow (100 ms on my computer, a few seconds on a smartphone). I would like to reduce the number of solutions, but all the obvious ways that I can think of are wrong. For example:

• Adding numbers instead of deleting them. . The advantage of this is that since minimal puzzles require at least 17 filled numbers, the first 17 numbers are guaranteed not to have a unique solution, reducing the number of solutions. Unfortunately, since the cells are visited randomly, many unnecessary digits will be added to one important digit, which “blocks” the unique solution. For example, if the first 9 cells added are in the same column, there is a lot of redundant information.
• If no other digit can replace the current, save it and do not solve the puzzle. . Since validation is thousands of times faster than solving the puzzle twice, this can be a huge time saver. However, just because no other legal figure now means that it will not be later as soon as we delete the other figures.
• Since we generated the original solution, we allow only once for each cell and see if it matches the original. This does not work, because the original solution can be anywhere in the search tree for possible solutions. For example, if the original solution is near the "left" side of the tree and we start the search on the left, we will skip the solutions on the right side of the tree.

I would also like to optimize the solution algorithm itself. The hard part determines if the solution is unique. I can do micro-optimization, for example, create a bitmask for legal placements for each cell, as described in this wonderful post . However, more complex algorithms, such as Dancing Links or simulated annealing, are not designed to determine uniqueness, but simply to find any solution.

How can I optimize my minimal Sudoku generator?

Answer 1

Here are the main optimizations that I implemented with a (very approximate) percentage increase in speed:

• Using bitmasks to track constraints (row, column, field) in each cell. This greatly speeds up the search for a placement, but slower to make a placement. The difficult factor in creating puzzles with bitmasks, and not just solving them, is that numbers can be deleted, which means that you need to track three types of restrictions as separate bits. A small further optimization is to store masks for each digit and each constraint in arrays. 40%
• Timing of generating and restarting if it takes too long. See here . The optimal strategy is to increase the waiting period after each unsuccessful generation to reduce the likelihood that it will continue indefinitely. 30% , mainly due to the reduction of the worst execution time.
• mbeckish and user295691 sentences (see comments on the original post). 25%

Answer 2

I have an idea on the 2nd option that you proposed, it would be better if you add 3 additional checks for the 1st 17 numbers

• find a list of 17 random numbers between 1-9

• add each item in a random place

  • these newly added numbers do not trigger 3 main sudoku criteria

    • no equal number on one line
    • no equal number in one column
    • no equal number in one 3x3 matrix

  • if condition 1 fails to go to the next column or row and check again 3 main criteria.

  • if the next row (i.e., in the 9th column or the 9th row) is not added to the 1st column after filling 17 characters, run your solution logic and find your unique solution.