Generating & Solving Sudoku in JS & Ruby with Backtracking

Update:

Thank you to edh_developer for helping me to identify an issue with multiple possible boards being generated. The gist code has been updated.

Sudoku

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:

1. 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.

2. 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.

3. 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

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.

---

Implementation

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.

Placement Criteria

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)

• To check the row, we can pick the row of 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.

• To check the column, we can examine the column index of 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.

• The region condition is trickier, because we must first determine which region the cell belongs to. Each region begins on rows 0, 3, and 6 and columns 0, 3, and 6. Using a combination of subtraction and modulus with the coordinates of the empty cell, we can determine the top-left most cell of the region which the cell belongs to. Then, we scan through the region and look for a match

• Since all three criteria must be met to pass, we can check that all conditions are met with a helper function.

Generating a Game Board

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:

• Obtain an empty 9x9 matrix filled with zeros.
• Scan the matrix for the next cell with a current value of zero.

• 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.

Generating a Playable Board

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.

Results

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.

Resources

• Use Backtracking to Solve Sudoku by: {% user christinamcmahon %}

• Sudoku Generator Algorithm by: 101Computing

Full Code <a name="full-code"></a>

• Javascript
• [Ruby] (#ruby)

Javascript - Full Code <a name="javascript"></a>

• JS Gist External Link

Ruby - Full Code <a name="ruby"></a>

• Ruby Gist External Link