codenewbie
javascript
ruby
algorithms
Published: Wed Feb 17 2021 (~ 6 min)
Read on Dev.toThank you to edh_developer for helping me to identify an issue with multiple possible boards being generated. The gist code has been updated.
Puzzle games like Sudoku have always fascinated me, and Sudoku in particular has helped me get through many long waits. It is a quite popular game, but for those unfamiliar with the rules here is a quick synopsis, or you can see the Wikipedia entry here.
A Sudoku game begins with a 9x9 grid partially filled with values from 1 to 9. The goal for the player, is to fill all of the remaining boxes with values from 1–9. However, each number that a player inserts must pass three strict rules:
Each value 1–9 can only be present once in a row. So in the example board above, 5, 3, and 7 cannot be written into any of the empty cells in the first row.
Each value 1–9 can only be present once in a column. So in the example board above, 5, 6, 8, 4, and 7 cannot be written into any of the empty cells in the first column.
Each value 1–9 can only be present once within a grid region. A grid region is a smaller 3x3 grid within the larger Sudoku board. These regions can be seen in the board above by their bolded borders. For example, the top-left region contains the values 5,3,6,8, and 9, and so these values cannot be placed again into any of the empty cells remaining in this region.
Solving these puzzles by hand involves meticulously comparing values against these rules and inserting them if they pass. Using similar logic in a backtracking algorithm, we can write a small script that can both generate and solve these boards as well. Let’s break it down here, or skip to the bottom for the full code.
Backtracking is an algorithmic approach to solving problems under specific constraints (sounds like Sudoku to me!) in which a value is entered if it meets the conditions and then the algorithm proceeds to the next value. However, if the algorithm is unable to place these subsequent values, it will backtrack to the last successfully placed value and change it to the next possible successful value and continue again.
I implemented the backtracking solution in both Javascript and Ruby. I have outlined the process and components in Javascript below, but the full code for both Ruby and Javascript can be found at the bottom of this article.
To begin implementing this algorithm, we must first define what our successful criteria are: rowSafe
checks the uniqueness of the values in the row, colSafe
checks it in the column and boxSafe
in the 3x3 grid. Then, we need to evaluate whether the coordinates of the emptyCell
(which is a JS object or Ruby hash containing both coordinates)
puzzleArray
that is specified in the emptyCell
coordinates and see if it contains the num
value we are trying to insert by looking for the index of that value.emptyCell
for each row and see if any of them contain that value. In Javascript .some()
will return true
if at least one of the values of array meet the condition.To generate a game board, we first start by making a completely filled, and correctly solved board out of a completely blank board. The range of values 1 to 9 is shuffled at the start of each iteration, ensuring the that probability of each new game being similar is low. Since each successful placement of a number will be followed by another attempt to place a number, this fillPuzzle
function will recursively call itself. Since this can get a bit tricky, let’s outline the steps before we see the code:
Randomize the array [0,1,2,3,4,5,6,7,8,9] and attempt to place the first value of that shuffled array into the empty cell found above.
Insert a conditional to abort the script if board fails to generate within a certain number of iterations. Most boards will generate in < 500ms, but random generation can lead to long wait times on occasion. I will discuss this more in the initialize section.
If the value from the shuffled array passes all of the safety checks, insert it and go back to step 2.
If the value from the shuffled array fails the safety check, return the cell to zero, and go back to the previously placed number and try to change it to the next possible value from the shuffled array and repeat.
Hooray! We have a completely filled Sudoku board that meets all of the criteria for the game! However, if you actually wanted to play the game, you need to “poke some holes” in it to make it playable. We can remove these cells at random; however, we must ensure that the removal of a value creates a board that can still be solved AND that it leads to a unique solution - as in there is only one way to place the numbers and win.
If the board can no longer be solved, or a second possible solution is found, we will put the value back and pick a different random cell to remove. As a bonus to this method, we can create an ordered list of the coordinates and value of each removed item if we ever need a hint. To this function we must pass in an integer number of holes to punch into the board. The more holes there are, the more difficult the board will be.
All that is left is to run the script and receive the startingBoard
, solvedBoard
, and list of removedVals
in an instant! Notice that in the initializing function newStartingBoard
we will try
to create a game. Most games will be created in <500 ms, but to prevent the occasional long wait, the iteration counter in fillPuzzle
will throw an error and abort the script after a specified time. We will catch
this error and use it to re-trigger the initialize function. It is faster to abandon puzzles with abnormally long generation times and start over than it is to wait them out.
And now join me in forever feeling incredibly slow when trying to solve these puzzles by hand.
Use Backtracking to Solve Sudoku by: {% user christinamcmahon %}