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?")