## 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:

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

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.

## Discussion (7)

In the puzzle generating code, I think it can generate and return puzzles with multiple solutions. Am I missing something that prevents that from happening?

Hi edh_developer, from what I have understood from looking into this, the process of generating the board, and then running the solve function to test the removal of each value to create a starting board should account for this. I haven't come across an edge case where this has not worked yet, so it is quite possible I could have missed something, or that my understanding is a bit off. If you have any specific advice I would be happy to chat with you about it and make any necessary revisions. Thank you!

Here's an example of a puzzle with two solutions:

sandwalk.blogspot.com/2007/06/i-kn...

It's possible for your code to randomly generate this puzzle, or one like it. The solver would then find one of the two solutions and return it, without checking for alternate solutions. It wouldn't catch the given example, and it may even return a different solution than the one you started with.

I tried it. I added this to the end of your source and ran it:

The resulting output:

$ ruby sudoku-full.rb

Original Puzzle:

9 2 6 | 5 7 1 | 4 8 3

3 5 1 | 4 8 6 | 2 7 9

8 7 4 | 9 2 3 | 5 1 6

---------------------

5 8 2 | 3 6 7 | 1 9 4

1 4 9 | 2 5 8 | 3 6 7

7 6 3 | 1

4 9| 8 2 5---------------------

2 3 8 | 7

9 4| 6 5 16 1 7 | 8 3 5 | 9 4 2

4 9 5 | 6 1 2 | 7 3 8

Generated Solution:

9 2 6 | 5 7 1 | 4 8 3

3 5 1 | 4 8 6 | 2 7 9

8 7 4 | 9 2 3 | 5 1 6

---------------------

5 8 2 | 3 6 7 | 1 9 4

1 4 9 | 2 5 8 | 3 6 7

7 6 3 | 1

9 4| 8 2 5---------------------

2 3 8 | 7

4 9| 6 5 16 1 7 | 8 3 5 | 9 4 2

4 9 5 | 6 1 2 | 7 3 8

Thank you! I was able to replicate this using a few different boards after your tip. I wrote a multipleSolutions check that now attempts to solve the puzzle from each of the currently empty positions and if more than one unique solution is found it will replace the removed value and attempt to remove a different one. I believe there is a more efficient solution, but this fix is working in the meantime for our app (fludoku.netlify.app). I coded the fix in JS first for the app, and will be working to update the ruby gist and gem to match. Thank you again!

The code works excellent down to 30 clues puzzles. It finds puzzles with 29 clues very slowly. Puzzles with 28 clues and less takes ages. (1-2 hours?) But Puzzles with 26 clues are very common. It is nearly impossible to find a puzzle with 26 clues.

This is a terrific blog post! Great piece of writing. I love how you guide a code newbie through this process. I’m so happy that you’re documenting your dev process along the way!