Step one of creating a Sudoku puzzle is filling in the whole 9 x 9 grid with numbers that fit the constraints of Sudoku rules.
-Each row must contain the numbers 1 to 9.
-Each column must contain the numbers 1 to 9.
-Each 3 x 3 local square must contain the numbers 1 to 9.
I decided to see how others tackled the task of creating Sudoku puzzles.
Some interesting pages I found were:
The last link is the one that sparked an idea for my own algorithm. The author explains how he wrote his program. It helped create a few good ideas to start my own Sudoku algorithm.
To fill the Sudoku grid I use, what I call, a 9 x 9 Potential Array. The Potential Array holds a list of possible values that could potentially work in each cell based on Sudoku rules.
With a blank 9 x 9 Sudoku Game Array, each cell in the Potential Array will be (1..9) as there are no limitations yet.
Staring with the first empty cell we randomly choose one of the potential numbers and remove the other potential numbers for this cell. This cell is set.
Each time we set a value for a cell we must recalculate the potential values for the cells in the 9 x 9 Potential Array that are not set. We do this based on the values for the set cells in the 9 x 9 Potential Array. For example, if there is a 7 in row 2, there can be no other 7’s in the rest of the row. Therefore the all the Potential Array lists for row 2 will be stripped of the number 7. The same holds true for the cells column and the local 3 x 3 square that the cell resides in. I continue to go through the cells in the 9 x 9 Potential Array that are not set, randomly choosing one of the possible values in that cell, setting that cell, and recalculating the new values for the cells that are not set.
If, while recalculating the values for cells that are not set in the 9 x 9 Potential Array, a cell has no possible values we cannot complete filling in this Sudoku board. So we must recurse back to the previous set cell, restoring previous values and try another value to set and continue again.
When we have reduced all the cells in the 9 x 9 Potential Array to only one possible value, we are done. We now have a fully filled in Sudoku board.