According to Wikipedia, Sudoku is a logic-based, combinatorial number-placement puzzle. In classic sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9.
These are the rules of the regular sudoku:
- Each row must contain every number from 1 to 9 exactly once.
- Each column, similarly, needs one of every number from 1 to 9.
- Each 3x3 ‘region’ needs to follow the same 1–9 pattern.
Knowing what a sudoku is and the rules of the game, we can write a Python program which takes a list containing the grid numbers and validate if such numbers make up a valid sudoku solution.
STEP 1: Define how to store a sudoku
There are many ways to store a sudoku board in Python. You could use tuples, sets, or even dictionaries to store the numbers for each cell in the grid.
In this tutorial, we will define a list containing 9 strings, which contains the 9 numbers for each row in the sudoku board.
Also, our program can receive a list containing 9 lists, where each list contains every number in a row as a string.
Below is the previous sudoku board arranged differently:
Optionally, but as a best practice, you can use this function to verify if the list you receive is a valid submission:
STEP 2: Write a reusable function to check repeated values in a row
So far, our program is able to receive a sudoku and check if it is a valid sudoku board. However, it still cannot tell if there are repeated numbers in a row, column, or region.
We can write a function that takes in a list (sudoku board), iterates its elements (rows), checks if there are repeated values, and returns True if there are repeated values or False if not.
To use this function, we will define two functions to extract the values of the sudoku in different orders.
STEP 3: Write a function that receives a board and returns a list with the columns
Based on how the sudoku is stored, the first digit of every element in the list represents the first column, the second digit represents the second column and so on.
This function will receive a sudoku board, iterate each row in the board, and store the nth digit of each row in a list. After storing a column, we will append the list to a parent list and continue with the next digits.
This is how the function looks like:
If we call this function with our sample sudoku as an argument, we get the following list:
print(to_column_list(sample1))>> [['2', '4', '8', '3', '6', '5', '7', '9', '1'],
['9', '3', '7', '8', '1', '4', '6', '2', '5'],
['5', '1', '6', '7', '2', '9', '3', '8', '4'],
['7', '8', '1', '4', '3', '2', '5', '6', '9'],
['4', '6', '9', '5', '8', '1', '2', '7', '3'],
['3', '5', '2', '9', '7', '6', '4', '1', '8'],
['8', '9', '5', '2', '4', '7', '1', '3', '6'],
['6', '2', '4', '1', '9', '3', '8', '5', '7'],
['1', '7', '3', '6', '5', '8', '9', '4', '2']]
If you want to return a list of strings instead of lists, you can replace the code in line 11 for the following:
return [''.join(row) for row in nth_digit]
Regardless of which return statement you use, the program can use both resulting lists.
Fun fact: nesting the same function an even number of times will return the original list.
Take a look:
STEP 4: Write a function that receives a board and returns a list with the regions
This one is a bit trickier than the previous function. Instead of iterating the whole row or column, we just want the 9 digits of each region in the board. For simplicity purposes, the function will iterate in a left-to-right, top-to-bottom fashion.
First, let’s store the top regions manually and check if there is a pattern we could use.
If you look closely, the range function receives two parameters: the start and stop numbers. The nested for loops increase these numbers by 3 to move to the next region.
Knowing this, we can put these for loops inside another for loop that returns 0–3–6, and add these values to the range parameters.
Just like this:
Similarly, let’s store the other rows of regions manually and check for any patterns.
Again, the range functions in lines 10, 22, and 34 increase their parameters by 3 each time. Finally, we can create one for loop to return 0–3–6 so we can move to the next row of regions.
Take a look at the final code for this step:
STEP 5: Put everything together
So far we have:
- A function that checks if there are repeated values in a row of a matrix.
- A function that verifies if sudoku board is valid. (OPTIONAL)
- A function that returns the nth value of the rows in a matrix.
- A function that returns a list with each sudoku region as a list.
Let’s define a function that takes in a sudoku, checks if it is a valid board, and resolves if it is a valid sudoku solution or not.
Congratulations! You have a Python program that validates sudoku solutions.