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 research problem it becomes
for the 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 a 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 exist. It is unknown whether or not there exists a well formed puzzle with only 16 clues.


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 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 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 the 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 value greater than 0, then we iterate for next column.
  • After checking if it is a safe place , we move to the next column and then assign num in current (row ,col) position of the grid. Later we check for next possibility with next column.
  • As our assumption was wrong, we discard the assigned num and then we go for the next assumption with 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.

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

And that’s it for building a sudoku solver in Python! I hope you had fun reading through the article and learned 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!