Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contain all of the digits from 1 to 9. The rule of the game is that you can not use the same number more then once in a given row or column.

To help us solve the puzzle in the above image we will put the numbers or the lack of it into a list of list or a 2D array, like so. As a side note, we pre-fill the empty fields we have in the puzzle with zeros.

grid [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]


And to helps us to a bit with the readability of the matrix we are going to utilize a package call numpy, which prints the matrix as we have above:

import numpy as np
print(np.matrix(grid))


To solve the puzzle we are going to use recursion. But first we need to write a helper function to check if it is actually possible to add a given number into a cell.

def possible(y, x, n):
global grid

# Check if a given number could be added in the row
for i in range(0, 9):
if grid[y][i] == n:
return False

# Check if a given number could be added in the column
for i in range(0, 9):
if grid[i][x] == n:
return False

# Then we check if we can add a given number into the sub-grid (square)
x0 = (x // 3) * 3
y0 = (y // 3) * 3

for i in range(0, 3):
for j in range(0, 3):
if grid[y0 + i][x0 + j] == n:
return False

return True


Now to actually solve the puzzle we iterate over the grid using recursion and backtracking.

def solve():
global grid

for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(y, x, n):
grid[y][x] = n
solve()  # Here we enter into our recursion
grid[y][x] = 0  # And if we got a bad solution we backtrack.
return  # We end up in a dead end we return

# Print solution
print(np.matrix(grid))

# We can use the follow "trick" to re-run the code to find more solutions
input("Solve again?")