A complete guide to solving a Sudoku puzzle with a recursive method
Sudoku is a popular Japanese puzzle game that is based on the logical placement of numbers. It doesn’t require any special mathematics skills or calculations. Let’s look at an example below from Wikipedia:
It is a 9x9 grid puzzle [81 squares]. At the beginning of the game, some squares are filled with digits, while most of them are empty. The goal of Sudoku is to fill those empty squares with digits so that each row, column, and 3×3 section contains numbers between 1 to 9. The players need to use logic to fill in the missing digits and complete the grid so that all the constraints and rules are satisfied. A move is incorrect if:
- Any row contains more than one of the same digit from 1 to 9.
- Any column contains more than one of the same digit from 1 to 9.
- Any 3×3 grid contains more than one of the same digit from 1 to 9.
Sudoku Solver [Brute Force Approach]
In this article, I will share how to solve the Sudoku puzzle above using a brute force approach.
First of all, let’s represent the puzzle as an 81-digit string:
Afterward, we can create the Sudoku Solver by following this three-step recursive procedure:
- Find the location of the first 0, denoted by
i
[i=0
means the first number,i=1
means the second, …, andi=80
means the last one .] If no 0 is found, a solution is found. - For location
i
, scan elements in the same row, same column, and same block. This step is to find all the digits for which locationi
cannot be filled. - Let location
i
try every possible value, one by one, and for each choice, repeat these three steps [until no 0 is found in step 1]. Every possible value = digit from 1 to 9 excluding those digits for which locationi
cannot be filled.
This brute force approach uses a recursive function that is similar to using an 81-level nested for
loop.
Step-by-Step Guide
Now let’s see how to implement it using code.
1. Find the location of the first 0
2a. How to tell if element i and element j are in the same row
From this code snippet, we can see that i//9=0
for i
in range[0, 9]
, i//9=1
for i
in range[9, 18]
, …, and i//9=8
for i
in range[72, 81]
.
2b. How to tell if element i and element j are in the same column
From this code snippet, we can see that i%9=0
for i
in [0, 9, 18, 27, 36, 45, 54, 63, 72]
, i%9=1
for i
in [1, 10, 19, 28, 37, 46, 55, 64, 73]
, …, and i%9=8
for i
in [8, 17, 26, 35, 44, 53, 62, 71, 80]
.
2c. How to tell if element i and element j are in the same block
From these code snippets, we can see that if elements i
and j
are in the same block, they will be in the same three rows and same three columns. Now let’s combine everything in step 2 to find all the digits for which location i
cannot be filled.
same row = {3, 5, 7}, same column = {8}, same block = {3, 5, 6, 8, 9}
∴
cannotuse = {3, 5, 6, 7, 8, 9}, every_possible_values = {0, 1, 2, 4}
Sudoku Solver Solution
Now let’s combine everything above and solve the Sudoku puzzle.
I hope you learned something from this tutorial.