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

Teaching Kids Programming: Videos on Data Structures and Algorithms

sudoku-solver

Given a Sudoku, we can use the Depth First Search Algorithm, Iterate Deepening Search Algorithm or Breadth First Search Algorithm to find solution(s). On the opposite, 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:

1. 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.
2. Remove a Random digit at a time
3. 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)
4. 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.
5. 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-3.5 (Open AI + Microsoft Azure):

1. Create a 9×9 grid and fill it with numbers from 1 to 9.
2. Randomly select a number from the grid and remove it.
3. Repeat step 2 until all numbers from the grid are removed.
4. Check if the grid is a valid Sudoku.
5. If the grid is valid, return it as the solution.
6. If the grid is not valid, repeat steps 2-5 until a valid solution is found.

–EOF (The Ultimate Computing & Technology Blog) —