How to generate Sudoku boards with unique solution

问题:

How do you generate a Sudoku board with a unique solution? What I thought was to initialize a random board and then remove some numbers. But my question is how do I maintain the uniqueness of a solution?

回答1:

Easy:

1. Find all solutions with an efficient backtracking algorithm.
2. If there is just one solution, you are done. Otherwise if you have more than one solution, find a position at which most of the solutions differ. Add the number at this position.
3. Go to 1.

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

回答2:

Here is the way my own SuDoKu program does it:

---

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

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

3. As long as the list is not empty, take the next position from the list and remove the number from the related cell.

4. Test uniqueness using a fast backtracking solver. My solver is - in theory - able to count all solutions, but for testing uniqueness, it will stop immediately when it finds more than one solution.

5. If the current board has still just one solution, goto step 3) and repeat.

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

7. Stop when you have tested all 81 positions.

---

This gives you not only unique boards, but boards where you cannot remove any 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 find a complete valid board first (randomly filled!) It works very similar, but "in the other direction":

---

1. Start with an empty board.

2. Add a random number at one of the free cells (the cell is chosen randomly, and the number is chosen randomly from the list of numbers valid for this cell according to the SuDoKu rules).

3. Use the backtracking solver to check if the current board has at least one valid solution. If not, undo step 2 and repeat with another number and cell. Note that this step might produce full valid boards on its own, but those are in no way random.

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

回答3:

You can cheat. Start with an existing Sudoku board that can be solved then fiddle 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 block row or block column you can swap single rows and single columns. Finally you can permute the numbers so there are different numbers in the filled positions as long as the permutation is consistent across the whole board.

None of these changes will make a solvable board unsolvable.

回答4:

Unless 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 The Another Solution Problem (ASP), where the goal is, given a problem and some solution, to find a different solution to that problem or to show that none exists. Yato then defined ASP-completeness, problems for which it is difficult to find another solution, and showed that Sudoku is ASP-complete. Since he also proves that ASP-completeness implies NP-hardness, this means that if you allow for arbitrary-sized Sudoku boards, there is no polynomial-time algorithm to check if the puzzle you've generated has a unique solution (unless P = NP).

Sorry to spoil your hopes for a fast algorithm!

回答5:

The solution is divide in to 2 parts:
A. Generating the number pattern 600 billion
B. Generating the masking pattern ~ 7e23 combinations

A ) For Number pattern the fastest way which can generate unique combinations with NO time spent on backtracing or testing

Step 1. Choose an already exiting matrix, I chose the below one as it can be made easily by human without any help from a computing device or solver:

First row is numbers in ascending order
Second row is also in ascending order but start from 4 & roll around
Third row is also in ascending order but start from 7 & roll around
Row 4,5,6: Replace the three cell column with the top right column - 2 5 8 and roll within the 3x3 cell for last column
Row 7,8,9: Replace the three cell column with the top right column - 3 6 9 and roll within the 3x3 cell for 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 the digits and replace in all other cells
Step 3. Randomly rearrange columns 1,2 and 3 within themselves
Step 4. Randomly rearrange columns 4,5 and 6 within themselves
Step 5. Randomly rearrange columns 7,8 and 9 within themselves
Step 6. Randomly rearrange rows 1,2 and 3 within themselves
Step 7. Randomly rearrange rows 4,5 and 6 within themselves
Step 8. Randomly rearrange rows 7,8 and 9 within themselves
Step 9. Randomly rearrange in 3 column groups of size 9x3
Step 10. Randomly rearrange in 3 row groups of size 3x9

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 Masking Pattern we need to have a solver algorithm. As we already have a quite unique number grid (which is also solved!) this gives us faster performance for using solver

Step 1: Start with selecting 15 random locations out of the 81.
Step 2: Check with solver whether it has unique solution
Step 3: If solution not unique select additional location. iterate Steps 2 and 3 until unique solution found

This should give you the very unique and fast Sudoku board.

回答6:

It's not easy to give a generic solution. You need to know a few things to generate a specific kind of Sudoku... for example, you cannot build a Sudoku with more than nine empty 9-number groups (rows, 3x3 blocks or columns). Minimum given numbers (i.e. "clues") in a single-solution Sudoku is believed to be 17, but number positions for this Sudoku are very specific if I'm not wrong. The average number of clues for a Sudoku is about 26, and I'm not sure but if you quit numbers of a completed grid until having 26 and leave those in a symmetric way, you may have a valid Sudoku. On the other hand, you can just randomly quit numbers from completed grids and testing them with CHECKER or other tools until it comes up with an OK.

回答7:

Here is a way to make a classic sudoku puzzle (sudoku puzzle with one and only solution; pre-filled squares are symmetrical around the center square R5C5).

1) start with a complete grid (using group filling plus circular shift to get it easily)

2) remove number(s) from two symmetrical squares if the cleared squares can be inferred using the remaining clues.

3) repeat (2) until all the 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 craft harder Sudoku puzzles. You may want to search "create classic sudoku" on YouTube to have a step by step example.

回答8:

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

But you can also use a SAT-solver, as opposed to writing an own backtracking algorithm. That way, you can to some extent regulate how difficult it will be to find a solution: If you restrict the inference rules that the SAT-solver uses, you can check whether you can solve the puzzle easily. Just google for "SAT solving sudoku".

回答9:

One way to generate sudoku faster.

1. find an exist sudoku.
2. exchange the value with a random group.
3. exchange the cell or the column or the row-grid or the column-grid.

You exchange the value will make the value different, if not exchange the rows or the column, the sudoku isn't changed in the essential.

You can flag the sudoku with 9 grids, the rows and column exchanged must do in the same grid. Like you can exchange row1-3, row4-6, row7-9, don't exchange row1-4 or row1-7. You can also exchange the row-grid(exchange row1~3 with the row4~6 or row7~9).

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