Solving Sudoku with Ruby

Remember that time when Sudoku was popular and hours just flew by as we pore over puzzles after puzzles? Well… me neither.

One of my early programming experience was at a bootcamp. At the end of the first week, we were supposed to write a program that solves a Sudoku puzzle. I couldn’t do it… And that bothered me… More than I cared to admit.

That was almost 2 years ago. I’d like to believe I’ve improved since then, so here’s my attempt at explaining how to write a program that solves a Sudoku puzzle. We’ll be doing it in Ruby, but the algorithm just uses for and while loops, so it should be easy enough to write in any other languages.

Overview

A Sudoku board consists of a 9x9 grid with numbers and blank spaces. The objective is to fill up all the blank spaces so that each row, grid, and 3x3 blocks contain numbers from 1 to 9.

To do that, we’ll break down the tasks into 7 functions:

• parse_board — takes an 81 character string — returns a 2-dimensional board array.
• find_empty_positions — takes a board array — returns the empty positions in it.
• check_row — takes a board array, row, and number — returns whether that number is valid in its row.
• check_col — takes a board array, column, and number — returns whether that number is valid in its column.
• check_block — takes a board array, row, column, and number — returns whether that number is valid in its 3x3 block.
• check_value — takes a board array, row, column, and number — returns whether that number is valid in its row, column, and 3x3 block.
• solve_puzzle — takes a board array — returns a solved board array.

If these seem vague, fret not. We’ll go through each of them and hopefully it’ll be clearer then.

Parse board

Before we start solving, we should think about the best data structure to represent our puzzle. Integers makes sense because we can perform mathematical operations on it (get the next/previous number for example). A 2-dimensional array makes it easier for us to visualise the puzzle.

Assuming we’re given an 81 character string to work with, we then need to convert it.

First, we’ll write the spec. We’ll declare the constants:

These are the values we’ll be testing throughout while building our solver. Declaring them upfront makes writing our test cleaner. Kind of like this:

Make sure it (and the other tests below) goes in the first block, right before the last end.

Now, we can write our first function and pass our test:

Just a short explanation here — our function will: loop through the string, find where the row breaks (index divisible by 9), slice the row string, split it into a row array, and convert each element to an integer.

Find empty positions

Now that we have our board in the right data structure, we can start solving it. First, we need to tell our program what to solve — the empty positions in the board.

Because we’ve structured our puzzle as a 2-dimensional array, a position can be represented as a pair of integers in an array: [row, col]. And we can retrieve the value on board position with: board[row][col].

Our function will receive a board and return an array of empty positions:

And this is what it looks like:

We’re using the same pattern as parse_board where we declare an array, loop through the rows in our board (the outer loop), loop through the columns (the inner loop), and if any value is 0, we’ll push its position into our array which we return at the end. We’ll be using this pattern A LOT.

Check row

check_row does exactly what its name implies — takes in a board, row number, and a number to check, then returns true if that number is valid in that row or false if it already exist. We can see here that the number 2 is not used yet in the first row, but 9 is:

As usual, we’ll write this function using the for loop:

Row is pretty straightforward to loop through — given a row number, we’ll run through all 9 columns of that row, and return false if our number exists. If the loop completes without finding our number, we return true.

Check Column

Similar to check_row, now we want a function that takes in a board, column number, and a number to check, then returns true if that number is valid for the column and false otherwise. Here, 9 is not in the first column so it’s valid but 5 is so it’s invalid:

Similar pattern as check_row, with a slight tweak here:

In check_row, we kept the row constant and loop through each column value and here we kept the column constant and loop through each row value. Otherwise, it’s the same pattern — break and return false if our loop found a value and return true if the loop is completed without finding any.

Check block

After row and column, the last thing we have to check is whether a number is valid in its 3x3 block. Similar to check_row and check_col, but we need both rows and column values here. We’ll test for position [2, 2] which is in the top-left block (where only the number 9 has been used):

We’ll be using the nested for loop pattern (again) here, except we first need to limit its scope to the right block:

A few things going on here. First, we determine the lower limit of our block’s row and column given a coordinate. The formula 3 * (row / 3) doesn’t make sense mathematically (the two 3s cancel each other out and we get back row), but Ruby rounds the result of divisions down. For example, 4 / 3 = 1 in Ruby so 3 * (4 / 3) = 3 — which is what we want.

The upper limit is just the lower limit plus 3. We’ve been using the ... range in all our for loops (which means from number…up to but not including), so this works well.

Once we know the upper and lower limit, we can apply the nested for loop pattern to run through both row and column. Note that we’re assigning the variable r and c here — because we’ve already used row and col as the function’s arguments.

Check value

Now that we know how to check rows, columns, and blocks, it would be convenient if we compose them together into a single function call. Our function will take in a board, row, column, and number, then return if that number is valid in its position:

Because we’ve done the heavy lifting in separate functions, this one is pretty straightforward:

We’re just calling check_row, check_col, and check_block, then returning true only if all of them are valid. Otherwise we return false.

Solve puzzle

We now have all the helper functions to write our solver, which will take in a board and list of empty positions, then return us the solution:

Simple enough, but under the hood, our function needs to do a couple of things:

A person solving a sudoku puzzle will look for the most obvious solutions first — like a row with 8 of its 9 values filled. Our solver is a lot dumber. It looks for the first empty position and takes a dumb guess of 1. If that is valid, it will then move to the next empty position and take another guess that it’s 1. If it’s not, it will take another guess that it’s 2 — moving on until it reaches 9. If it reaches 9, meaning none of its guesses are valid — then it tracks back to the previous empty position and takes another guess there. On and on until it gets a valid guess on the last empty position.

We’re using a while loop here (instead of for) because that lets us track back. The first while loop iterates through empty_positions. At each empty position, we find the current value on the board (at first run, this will be 0 at each position). Our first guess is the next number (1 at first run), and run our second loop.

If our first guess is valid, this loops terminates immediately and we move on to the next empty position. If our guess in not valid, this loop continues and we guess the next number.

Our second will guess each number from 1 to 9, and if a solution is still not found, we track back to the previous empty position and take another guess there.

Whew, I hope that made sense.

Putting It All Together

We can take this a step further and compose everything we did in a single function that takes a board string and returns a solution:

This function simply calls all the function we’ve written to work together to convert a string into a board, find its empty position, and solve it:

That’s it, we’re done!

Conclusion

If you’ve gone through all that, first of all, thank you! I hope that made sense and please let me know if it didn’t.

This solution should work for every level of sudoku puzzles with a solution, and solve it within mili-seconds. But in terms of being efficient, it really is not. It also has a potential of running infinitely if given a board with no solution. You might want to work to improve these.