ECX 30 Days of Code and Design
Day 30
Sudoku Solver
Task
- Write a function that takes in a 9×9 array of numbers. Let this list represent a partially filled grid of numbers (specifically; integers ranging from 1 to 9, where "0" signifies an empty space in the grid) as parameters, and return a filled 9×9 array, the solution to it. If there are no solutions, return False.
Exceptions:
- If an empty list or an invalid list (list with numbers outside the 1-9 range, or empty lists, or a list of the wrong size, etc.) is input, it issues a warning. Hint: Backtracking is one effective method for solving this problem—it is however not the only method.
The problem is further explained below.
Given a partially filled 9×9 list, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and sub-grid of size 3×3 contains exactly one instance of the digits from 1 to 9.
My Approach
Full Code
This is the full code below. I will explain it in bits throughout this article.
def is_valid_move(grid, row, col, number):
"""Checks if the number inputted is a valid move."""
# Check the row for repeated number
for x in range(9):
if grid[row][x] == number:
return False
# Check the columns for repeated number
for x in range(9):
if grid[x][col] == number:
return False
# Check the 3 by 3 square for repeated number
corner_row = row - row % 3
corner_col = col - col % 3
for x in range(3):
for y in range(3):
if grid[corner_row + x][corner_col + y] == number:
return False
return True
def solve(grid, row, col):
"""Solves the sudoku"""
try: # This handles a wrong type found in the grid
# If we are at the last column and row, and all digits have been inputted,
# the board is filled and the game ends
if col == 9:
if row == 8:
return True
# This takes us to the beginning of a new row when col = 9
row += 1
col = 0
# Recurse the function if the cell is not empty (that it is not empty).
if grid[row][col] > 0:
return solve(grid, row, col + 1)
# Try the numbers 1 - 9 in an empty slot (slot having the number 0).
for num in range(1, 10):
# Check if the number is valid and enter the valid number into the cell
if is_valid_move(grid, row, col, num):
grid[row][col] = num
if solve(grid, row, col + 1):
return True
grid[row][col] = 0
return False
except TypeError:
print('Invalid input!')
grids = [[0, 0, 8, 7, 0, 4, 0, 0, 3],
[1, 0, 7, 3, 0, 0, 2, 0, 0],
[3, 0, 2, 0, 0, 0, 6, 0, 7],
[0, 0, 0, 0, 0, 0, 5, 0, 0],
[7, 0, 0, 0, 0, 5, 1, 6, 0],
[0, 8, 0, 0, 3, 1, 0, 7, 0],
[0, 0, 6, 0, 0, 8, 0, 0, 5],
[4, 0, 0, 0, 5, 0, 0, 0, 0],
[8, 5, 0, 9, 4, 0, 0, 0, 0]]
# Function to print board
def print_board():
"""Prints the sudoku board"""
print(' Sudoku Board '.center(21, '*'))
for i in range(9):
for j in range(9):
print(grids[i][j], end=' ')
if (j + 1) % 3 == 0 and j != 8:
print('|', end=' ')
print()
if (i + 1) % 3 == 0 and i != 8:
print('---------------------')
if i == 8:
print('\n')
# Function call
print_board()
if solve(grids, 0, 0):
print(' Solved Board '.center(21, '*'))
for k in range(9):
for l in range(9):
print(grids[k][l], end=' ')
if (l + 1) % 3 == 0 and l != 8:
print('|', end=' ')
print()
if (k + 1) % 3 == 0 and k != 8:
print('---------------------')
else:
print('No Solution For This Sudoku')
Function to Check if an Input Can Be in a Cell
First, we define a function, is_valid_move(), which is used to check if a number is already in a given row, column, or 3 by 3 small square. corner_row = row - row % 3 and corner_col = col - col % 3 is used to define our 3 by 3 square; for example, if we are to input a number in row 7 and column 4, corner_row = row - row % 3 ( 7 – (7%3) = 7 – 1 = 6) and corner_row = row - row % 3 (4 – (4%3) = 4 – 1 = 3) takes us to the beginning of the small square and using two for loops at a range of 3, we check if the number we are inputting is already within the square. If the number is either within the square, the row, or the column, we return False, else, we return True.
def is_valid_move(grid, row, col, number):
"""Checks if the number inputted is a valid move."""
for x in range(9):
if grid[row][x] == number:
return False
for x in range(9):
if grid[x][col] == number:
return False
corner_row = row - row % 3
corner_col = col - col % 3
for x in range(3):
for y in range(3):
if grid[corner_row + x][corner_col + y] == number:
return False
return True
Function to Solve the Sudoku
Next, we define the function which solves the sudoku board. Using an if statement, we check if the board has already been solved. When col = 9 and row = 8 it means the whole board has been filled. But if row != 8 and col = 9, it means that we have exceeded that row, thus we move to the next row. Using grid[row][col] > 0:, we check if the slot is empty (as 0 indicates an unfilled space); if it is not empty, we move to the next column in that row by recursing solve(grid, row, col + 1), but if it is empty, we would call is_valid_move() function and check from 1 to 9 which of the numbers is a valid move in that space. We would wrap the code in a try except block to handle values other than integers.
def solve(grid, row, col):
"""Solves the sudoku"""
try:
if col == 9:
if row == 8:
return True
row += 1
col = 0
if grid[row][col] > 0:
return solve(grid, row, col + 1)
for num in range(1, 10):
if is_valid_move(grid, row, col, num):
grid[row][col] = num
if solve(grid, row, col + 1):
return True
grid[row][col] = 0
return False
except TypeError:
print('Invalid input!')
Sudoku Board Input
Next, we store the sudoku board in a variable, grids, using nested lists.
grids = [[0, 0, 8, 7, 0, 4, 0, 0, 3],
[1, 0, 7, 3, 0, 0, 2, 0, 0],
[3, 0, 2, 0, 0, 0, 6, 0, 7],
[0, 0, 0, 0, 0, 0, 5, 0, 0],
[7, 0, 0, 0, 0, 5, 1, 6, 0],
[0, 8, 0, 0, 3, 1, 0, 7, 0],
[0, 0, 6, 0, 0, 8, 0, 0, 5],
[4, 0, 0, 0, 5, 0, 0, 0, 0],
[8, 5, 0, 9, 4, 0, 0, 0, 0]]
Function to Display the Sudoku Board
Next, we define a function, print_board(), which prints the above board in a pretty format. After every 3 numbers, a pipe (|) is printed to demarcate the square. Also, after every 3 columns, dashes (------) are printed.
def print_board():
"""Prints the sudoku board"""
print(' Sudoku Board '.center(21, '*'))
for i in range(9):
for j in range(9):
print(grids[i][j], end=' ')
if (j + 1) % 3 == 0 and j != 8:
print('|', end=' ')
print()
if (i + 1) % 3 == 0 and i != 8:
print('---------------------')
if i == 8:
print('\n')
print_board()
Displaying the Solved Sudoku Board
Finally, using an if statement we check if the sudoku grid was solvable, if yes, we print it out in a pretty format; else, we display on the screen that there is no solution for the sudoku.
if solve(grids, 0, 0):
print(' Solved Board '.center(21, '*'))
for k in range(9):
for l in range(9):
print(grids[k][l], end=' ')
if (l + 1) % 3 == 0 and l != 8:
print('|', end=' ')
print()
if (k + 1) % 3 == 0 and k != 8:
print('---------------------')
else:
print('No Solution For This Sudoku')
There you have it. In case of questions and suggestions, kindly drop a comment. Thank you.
Run the code on Replit.