How to create sudoku boards with unique solutions

Question

How do you create a Sudoku board with a unique solution? I decided to initialize a random board and then delete some numbers. But my question is how to preserve the uniqueness of the solution?

Answer 1

Simply:

• Find all solutions with an effective reverse tracking algorithm.
• If there is only one solution, everything is ready. Otherwise, if you have multiple solutions, find a position in which most solutions differ. Add a number at this position.
• Go to 1.

I doubt that you can find a solution that will be much faster than that.

Answer 2

Here's how my own SuDoKu program does it:

---

1. Start with a full, valid board (filled with 81 numbers).

2. Make a list of all 81 cell positions and shuffle it randomly.

3. While the list is not empty, take the next item from the list and remove the number from the linked cell.

4. Check for uniqueness using the fast reverse tracking solver. My solver - theoretically - is able to count all the solutions, but to check for uniqueness, he will immediately stop when he finds more than one solution.

5. If the current board has only one solution, go to step 3) and repeat.

6. If the current board has more than one solution, undo the last delete (step 3) and continue step 3 from the next position from the list

7. Stop when you check all 81 positions.

---

This gives you not only unique boards, but also boards on which you cannot remove more numbers without destroying the uniqueness of the solution.

Of course, this is only the second half of the algorithm. The first half is to first find a complete valid board (randomly filled!). It works very similarly, but "in a different direction":

---

1. Start with an empty board.

2. Add a random number to one of the free cells (the cell is randomly selected, and the number is randomly selected from the list of numbers valid for this cell in accordance with SuDoKu rules).

3. Use the backtracking solver to check if there is at least one valid solution on the current board. If not, cancel step 2 and repeat with a different number and cell. Please note that this step can create full-fledged boards yourself, but they are by no means random.

4. Repeat until the board is completely filled with numbers.

Answer 3

You can cheat. Start with your existing Sudoku board, which can be solved, and then play with it.

You can swap any row of three 3x3 blocks with any other row. You can swap any column of three 3x3 blocks with another column. Within each row of a block or block column, you can change individual rows and separate columns. Finally, you can rearrange the numbers so that the filled positions have different numbers if the permutation is consistent across the board.

None of these changes will make a solvable board unsolvable.

Answer 4

If P = NP, there is no polynomial time algorithm for generating general Sudoku problems with exactly one solution.

In his master's thesis, Takayuki Yato defined “Another Problem of Solution” (ASP), where the goal is to solve a problem and some solution, find another solution to this problem or show that no one exists. Yato then determined the ASP-completeness, problems for which it is difficult to find another solution, and showed that Sudoku is ASP-complete. Since it also proves that ASP completeness implies NP hardness, this means that if you allow sudoku boards of arbitrary size, there is no polynomial time algorithm to check if the puzzle you created has a unique solution (if only P = NP).

Sorry to spoil your hopes for a fast algorithm!

Answer 5

It is not easy to give a general solution. You need to know a few things to create a particular type of sudoku ... for example, you cannot build a sudoku with more than nine empty 9-digit groups (rows, 3x3 blocks or columns). The minimum given numbers (ie, “Hints”) in a single Sudoku decision are believed to be 17, but the numerical positions for this Sudoku are very specific, if I'm not mistaken. The average number of hints for sudoku is about 26, and I'm not sure, but if you leave the numbers of the filled grid to 26 and leave them symmetrically, you may have a valid sudoku. On the other hand, you can just accidentally leave the number of ready-made grids and check them with CHECKER or other tools until OK appears.

Answer 6

Here's a way to make a classic sudoku puzzle (a one-and-one solution sudoku puzzle, pre-filled squares are symmetrical around the central square R5C5).

1) start with a full grid (using group padding plus a circular shift to get it easy)

2) remove the number from the two symmetric squares if the cleared squares can be deduced using the remaining keys.

3) repeat (2) until all numbers are checked.

Using this method, you can create a very easy sudoku puzzle with or without programming. You can also use this method to create more complex Sudoku puzzles. You can search “create classic sudoku” on YouTube for a step-by-step example.

Answer 7

The solution is divided into 2 parts:
A. Generation of a 600 billion number template
B. Masking Pattern Generation ~ 7e23 Combinations

A) For a number template, the fastest way that can generate unique combinations without spending time searching or testing

Step 1. Select an existing matrix, I chose the following, since it can be easily made by a person without any help from a computing device or solver:

First line - numbers in ascending order
The second row is also in ascending order, but starts at 4 and rotates around
The third row is also in ascending order, but starts at 7 and rotates around
Row 4,5,6: replace the column of three cells with the upper right column - 2 5 8 and flip the 3x3 cell for the last column.
Row 7,8,9: replace the column of three cells with the upper right column - 3 6 9 and flip the 3x3 cell for the last column.

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

Step 2. Shuffle the numbers and replace all other cells
Step 3. Arbitrarily rearrange columns 1,2 and 3 inside yourself
Step 4. Arbitrarily rearrange columns 4,5 and 6 inside itself
Step 5. Arbitrarily rearrange columns 7.8 and 9 inside yourself
Step 6. Arbitrarily rearrange rows 1,2 and 3 inside yourself
Step 7. Arbitrarily rearrange rows 4,5 and 6 inside yourself
Step 8. Arbitrarily rearrange rows 7.8 and 9 inside yourself
Step 9. Arbitrarily rearrange into 3 groups of 9x3 columns
Step 10. Arbitrarily rearrange in 3 rows of 3x9 rows

voila ...

5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 3 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3

B) For the masking template, we need a decisive algorithm. Since we already have a rather unique grid of numbers (which is also solvable!), This gives us better performance when using the solver

Step 1: Start by choosing 15 random spots out of 81.
Step 2: Check with the solver if it has a unique solution
Step 3: If the solution is not unique, select an additional location. repeat steps 2 and 3 until a unique solution is found

This should give you a very unique and fast sudoku board.

Answer 8

I also believe that you will have to explicitly check the uniqueness. If you have less than 17 givens, a unique solution is very unlikely: although it has not yet been found, although it is not yet clear whether it can exist.)

But you can also use a SAT solver rather than writing your own backtracking algorithm. Thus, you can adjust to some extent how difficult it will be to find a solution: if you restrict the inference rules used by the SAT solver, you can check whether you can solve the puzzle easily. Just google for "SAT Sudoku Solutions."

Answer 9

One way to generate sudoku is faster.

1. find an existing sudoku.
2. exchange value with a random group.
3. swap a cell or column, or a grid of columns, or a grid of columns.

If you change the value, it will become different; if you do not change the row or column, Sudoku will not change basically.

You can mark sudoku with 9 grids, the exchange of rows and columns should be performed in the same grid. As you can change lines 1-3, lines 4-6, lines 7-9, do not exchange lines 1-4 or lines 1-7. You can also change the grid of lines (change line 1 ~ 3 to line 4 ~ 6 or line 7 ~ 9).

Solve Sudoku: write empty with all possible values, then check the value from 1 to 9. If one value is unique, remove it from the loop.