DEV Community

loading...
Cover image for Generating & Solving Sudoku  in JS & Ruby with Backtracking

Generating & Solving Sudoku in JS & Ruby with Backtracking

dsasse07 profile image Daniel Sasse Updated on ・6 min read

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.

Sudoku Starting Board


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

Sudoku Starting Board

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.

Sudoku Backtracking Animation

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.

Generated Sudoku Boards: Solved, Starting, Removed Values

And now join me in forever feeling incredibly slow when trying to solve these puzzles by hand.

Amateur Hour

Resources

Full Code

Javascript - Full Code

Ruby - Full Code

Discussion (6)

pic
Editor guide
Collapse
edh_developer profile image
edh_developer

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?

Collapse
dsasse07 profile image
Daniel Sasse Author

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!

Collapse
edh_developer profile image
edh_developer

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.

Thread Thread
edh_developer profile image
edh_developer

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

def printboard(board)
  i = 1
  for row in board
    puts "#{row[0]} #{row[1]} #{row[2]} | #{row[3]} #{row[4]} #{row[5]} | #{row[6]} #{row[7]} #{row[8]}"
    if i == 3 || i == 6 then puts "---------------------" end
    i += 1
  end
end

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, 4, 9, 8, 2, 5],
    [2, 3, 8, 7, 9, 4, 6, 5, 1],
    [6, 1, 7, 8, 3, 5, 9, 4, 2],
    [4, 9, 5, 6, 1, 2, 7, 3, 8]
]
# Could have been randomly generated by
# poke_holes(SOLUTION,52)
PUZZLE = [
    [9, 0, 6, 0, 7, 0, 4, 0, 3],
    [0, 0, 0, 4, 0, 0, 2, 0, 0],
    [0, 7, 0, 0, 2, 3, 0, 1, 0],
    [5, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 4, 0, 2, 0, 8, 0, 6, 0],
    [0, 0, 3, 0, 0, 0, 0, 0, 5],
    [0, 3, 0, 7, 0, 0, 0, 5, 0],
    [0, 0, 7, 0, 0, 5, 0, 0, 0],
    [4, 0, 5, 0, 1, 0, 7, 0, 8]
]

puts "\nOriginal Puzzle:\n\n"
printboard(SOLUTION)

puts "\n\nGenerated Solution:\n\n"
printboard(Sudoku.new.solve(PUZZLE))
Enter fullscreen mode Exit fullscreen mode

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 1
6 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 1
6 1 7 | 8 3 5 | 9 4 2
4 9 5 | 6 1 2 | 7 3 8

Thread Thread
dsasse07 profile image
Daniel Sasse Author

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!

Collapse
sylwiavargas profile image
Sylwia Vargas

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!