Teaching Kids Programming – How to Design a Random Sudoku? Algorithm to Design a Random Sudoku | ninjasquad
Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a Sudoku, we can use the Depth First Search Algorithm, Iterate Deepening Search Algorithm or Breadth First Search Algorithm to find solution(s). If we are to design an algorithm that would generate a valid sudoku, we need to clarify the following:
- Does the Sudoku have to be in a solvable state? Yes
- Does the Sudoku have many solutions? We can assume the returned Suduoku have only 1 unique solution
- How difficult to solve the Sudoku? We can make a parameter for this: easy, medium or difficult
There are 6.671×10^21 valid sudoku states, and if we ignore duplicate like rotated, mirrored states, the number is brought down to 5.4×10^9 states. We can randomly generate a matrix filled with numbers 1-9, and check if it is a valid sudoku, but this is extremely inefficient, as the generated matrix is most unlikely to be valid sudoku.
Algorithm to Design a Random Sudoku
To design an efficient algorithm that would generate a Random Valid Sudoku, we can use the following approach:
- Use a Backtracking (Depth First Search) Algorithm to generate a valid complete sudoku with randomness e.g. Instead of trying filling numbers from 1 to 9, we can shuffle the selection of numbers.
- Remove a Random digit at a time
- Check if the sudoku state is solvable and only contains one solution (using Depth First Search Algorithm aka Back Tracking, or Breadth First Search Algorithm)
- If it is, and we have not removed N digits, we go back to step 2. The number of digits to remove corresponds to level of difficulty. More digits removed, harder the sudoku state and vice versa.
- If it is nor solvable neither having one solution, we have to put the digit back, and retry with another random digit (step 2)
Here is the answer from the ChatGPT (Open AI + Microsoft Azure):
- Create a 9×9 grid and fill it with numbers from 1 to 9.
- Randomly select a number from the grid and remove it.
- Repeat step 2 until all numbers from the grid are removed.
- Check if the grid is a valid Sudoku.
- If the grid is valid, return it as the solution.
- If the grid is not valid, repeat steps 2-5 until a valid solution is found.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
a WordPress rating system
Last Post: How to Map or Transform a Vector in C++ (Template Function)?