Sudoku Solver in Python

Sudoku solver in Python

Let’s build a sudoku solver in Python today! Sudoku Puzzle is a very popular puzzle that appears in the daily newspaper that attracts the attention of a lot of people. There are a lot of difficult, unsolved problems about sudoku puzzles and their generalizations which makes this puzzle interesting, specifically to a lot of mathematics lovers.


What is a Sudoku Puzzle?

In the Sudoku puzzle, we need to fill in every empty box with an integer between 1 and 9 in such a way that every number from 1 up to 9 appears once in every row, every column, and every one of the small 3 by 3 boxes highlighted with thick borders.

The difficulty of this puzzle might vary. The more the difficulty level of Sudoku puzzles, the more challenging the research problem it becomes for computational scientists. Difficult puzzles mostly have less prescribed symbols.

The Sudoku puzzles which are published for entertainment have unique solutions. A Sudoku puzzle is believed to be well-formed if it has a unique solution. Another challenging research problem is to determine how few boxes need to be filled for a Sudoku puzzle to be well-formed. Well-formed Sudoku with 17 symbols exists. It is unknown whether or not there exists a well-formed puzzle with only 16 clues. The lesser the clues, the higher the chances of multiple solutions.


Steps to solve the Sudoku Puzzle in Python

  • In this method for solving the sudoku puzzle, first, we assign the size of the 2D matrix to a variable M (M*M).
  • Then we assign the utility function (puzzle) to print the grid.
  • Later it will assign num to the row and col.
  • If we find the same num in the same row or same column or in the specific 3*3 matrix, ‘false’ will be returned.
  • Then we will check if we have reached the 8th row and 9th column and return true for stopping further backtracking.
  • Next, we will check if the column value becomes 9 then we move to the next row and column.
  • Further now we see if the current position of the grid has a value greater than 0, then we iterate for the next column.
  • After checking if it is a safe place, we move to the next column and then assign the num in the current (row, col) position of the grid. Later we check for the next possibility with the next column.
  • As our assumption was wrong, we discard the assigned num and then we go for the next assumption with a different num value

Implementing the Sudoku Solver in Python

We’ll use the backtracking method to create our sudoku solver in Python. Backtracking means switching back to the previous step as soon as we determine that our current solution cannot be continued into a complete one. We use this principle of backtracking to implement the sudoku algorithm. It’s also called the brute force algorithm way to solve the sudoku puzzle.

M = 9
def puzzle(a):
	for i in range(M):
		for j in range(M):
			print(a[i][j],end = " ")
		print()
def solve(grid, row, col, num):
	for x in range(9):
		if grid[row][x] == num:
			return False
		    
	for x in range(9):
		if grid[x][col] == num:
			return False


	startRow = row - row % 3
	startCol = col - col % 3
	for i in range(3):
		for j in range(3):
			if grid[i + startRow][j + startCol] == num:
				return False
	return True

def Suduko(grid, row, col):

	if (row == M - 1 and col == M):
		return True
	if col == M:
		row += 1
		col = 0
	if grid[row][col] > 0:
		return Suduko(grid, row, col + 1)
	for num in range(1, M + 1, 1): 
	
		if solve(grid, row, col, num):
		
			grid[row][col] = num
			if Suduko(grid, row, col + 1):
				return True
		grid[row][col] = 0
	return False

'''0 means the cells where no value is assigned'''
grid = [[2, 5, 0, 0, 3, 0, 9, 0, 1],
        [0, 1, 0, 0, 0, 4, 0, 0, 0],
	[4, 0, 7, 0, 0, 0, 2, 0, 8],
	[0, 0, 5, 2, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 9, 8, 1, 0, 0],
	[0, 4, 0, 0, 0, 3, 0, 0, 0],
	[0, 0, 0, 3, 6, 0, 0, 7, 2],
	[0, 7, 0, 0, 0, 0, 0, 0, 3],
	[9, 0, 3, 0, 0, 0, 6, 0, 4]]

if (Suduko(grid, 0, 0)):
	puzzle(grid)
else:
	print("Solution does not exist:(")

Output:

====================== RESTART: C:/Users/SIDDHI/sudoku.py ===========
2 5 8 7 3 6 9 4 1 
6 1 9 8 2 4 3 5 7 
4 3 7 9 1 5 2 6 8 
3 9 5 2 7 1 4 8 6 
7 6 2 4 9 8 1 3 5 
8 4 1 6 5 3 7 2 9 
1 8 4 3 6 9 5 7 2 
5 7 6 1 4 2 8 9 3 
9 2 3 5 8 7 6 1 4 

Conclusion

That’s all for building a sudoku solver in Python! I hope you had fun reading through the article and learning how we implemented the code.

Psst… there’s also an easier way to build a sudoku solver in Python!

You can import the sudoku py-sudoku.PyPI module from https://pypi.org/project/py-sudoku/. It is a simple Python program that generates and solves m x n Sudoku puzzles.

Pretty cool, ain’t it? Now it’s time for you to play around with sudoku puzzles!

What’s Next?

Resources