Algorithm Design for Random Sudoku Game (Sudoku)

sudoku-solver

Given a Sudoku, we can use a depth-first search algorithm, an iterative deepening search algorithm, or a breadth-first search algorithm to find possible solutions. Conversely, if we are to design an algorithm to generate valid Sudoku, we need to clarify the following questions:

• Must the generated Sudoku have a solvable state? Yes
• Does the generated Sudoku have multiple solutions? We can assume that the returned Suduoku has only 1 unique solution
• How difficult is the generated Sudoku? We can set a parameter for this: easy, medium or hard

There are a total of 6.671×10^21 valid Sudoku states, and this number drops to 5.4×10^9 states if we ignore repeated states such as rotations, mirroring states, etc. We could randomly generate a matrix filled with the numbers 1-9 and check if it is a valid Sudoku, but this is very inefficient because the resulting matrix most likely will not be a valid Sudoku.

Design an Algorithm for Random Sudoku

In order to design an efficient algorithm to generate a random valid Sudoku, we can use the following algorithm:

1. Use a backtracking (depth-first search) algorithm to generate a valid complete Sudoku with randomness. For example, instead of trying to fill in the numbers 1 through 9 in sequence, we could choose numbers at random.
2. Delete a random number each time
3. Check if the Sudoku state is solvable and contains exactly one solution (using a depth-first search algorithm, also known as backtracking or breadth-first search algorithm)
4. If yes, proceed to step 2, if we have not removed N numbers. The number of numbers to remove corresponds to the difficulty level. Removing more numbers makes the sudoku state harder and vice versa.
5. If it is neither solvable nor has a solution, we have to put the number back and try again with another random number (step 2)

Here’s the answer from ChatGPT 3.5 (Open AI + Microsoft Azure):

1. Create a 9×9 grid and fill it with numbers 1 through 9.
2. Pick a number at random and delete it.
3. Repeat step 2 until all numbers are removed from the grid.
4. Checks if the grid is a valid sudoku.
5. If the mesh is valid, it is returned as the solution.
6. If the mesh is not valid, repeat steps 2-5 until a valid solution is found.

English: Teaching Kids Programming – How to Design a Random Sudoku? Algorithm to Design a Random Sudoku

There are a total of 665 Chinese characters in this article, count it right.

¥ tipping support

Scan the QR code and share this article to WeChat Moments