**Definition:**

**Sudoku Solver Python Backtracking Recursion :** Sudoku is a simple numbers game that uses a grid of 9 x 9 fields. A number from 1 to 9 will be entered in the box. A number cannot appear twice in any row or column. So today, let’s try out a Sudoku solver Python program. Click here to get the complete code. A large box is formed from 3 x 3 smaller boxes. The same rules apply, numbers cannot be repeated within the large box.

Sudoku puzzles can be solved in many different ways, but here we will write a simple program to solve it using Python. This will take a few minutes and I won’t use any modules or anything complicated to keep it simple. However, when coding a program like this, there are an infinite number of possible solutions. Let’s use two methods that will make your program easier and run faster. The two important methods we will discuss are recursion and backtracking.

### Recursion

Recursion involves calling functions within functions. This would be understandable if you need to call a function multiple times to solve for an unknown number.

### Backtracking

Backtracking inserts possible numbers into the next empty box and moves on to the next unresolved box. This continues until an error occurs and I enter zero in the field. Go to the previously resolved field and try to resolve it using the next possible number.

### Loading a board

So let’s get to it. We first need to load a board that we will have to solve:

board=[ [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]]

When printing out this board, it might look messy. We use a “print_board” to make the board look neater.

#We shorten the board name to bo for easy usage def print_board(bo): for i in range(len(bo)): if i%3 == 0 and i!=0: print("---------------------") #This prints a horizontal line between the bigger boxes for j in range(len(bo[0])): if j%3 == 0 and j!=0: print(" | ", end ="") if j==8: print(bo[i][j]) else: print(str(bo[i][j]) + " ",end="") #This prints a vertical line between the bigger boxes

### Finding empty slots

To solve the sudoku, we first need to find an empty box. We define a function for this. The function returns the position of the empty box denoted by zero. It returns None if there are no more empty boxes which means that the puzzle has been solved.

def find_empty(bo): for i in range(len(bo)): for j in range(len(bo[0])): if bo[i][j] == 0: return (i, j) return None

Once we have located the empty boxes, we need a function that checks possible solutions for each box. This means you need to check if the number appears in the same column, same row, or inside a large box. These are the three things you need to check.

### Validity of a number to be inserted

The function defined here takes three parameters. The board, the number you are checking, and the position within the board where you want to insert it. If the number occurs within the above three cases, it returns False and the new value is inserted. If all three cases pass, return True and proceed to the next unresolved field.

def valid(bo, num, pos): #We first check if the number has occurred within the row for i in range(len(bo[0])): if bo[pos[0]][i] == num and pos[1]!= i: return False #We then check if the number has occurred within the column for j in range(len(bo)):#checking column if bo[i][pos[1]] == num and pos[0]!= i: return False #We finally check if the number has occurred within the bigger box box_x = pos[1]//3 box_y = pos[0]//3 for i in range(box_y*3, box_y*3 + 3): for j in range(box_x*3, box_x*3 + 3): if bo[i][j] == num and (i,j) != pos: return False return True

### Solving the sudoku puzzle

After all this work, we can finally reach the final function. This is very important. The solve function uses the board as a parameter. First, find an empty space on the Sudoku board. After that, you should check if the problem is resolved. If yes, return True and exit the function. If not, update a new empty slot. Now, if possible, try filling the empty slots with numbers 1 through 9. Check if the number can be inserted and if so insert it. To move to the next empty slot, repeat the same process until there are no more empty slots. Hence the term recursion. We remember the function itself.

However, we do this to find a possible solution and if we run into a dead end we backtrack. This means that we replace the slot we just filled with a zero and move back to the previously solved slot and try the next possible solution.

def solve(bo): find = find_empty(bo) if not find: #This means that the find function came back null. #This implies that the sudoku has been solved. return True else: row, col = find for i in range(1,10): if valid(bo, i , (row,col)): #If the number can be plugged in at the empty slot, we insert it. bo[row][col] = i #We then recall the function to solve the next empty slot. if solve(bo): return True #When we run into an error, we backtrack. #We do this by placing a zero to the previously solved slot. bo[row][col]=0 return False

We finish off by printing the board before the solution and calling the solve function. We insert a line to differentiate the solved board and the unsolved board. And we print the finished board. We use the custom print function to print out the boards neatly.

print_board(board) solve(board) print("Solving") print_board(board)

Let us now see the finished code combining the above functions and board.

board=[ [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]] def print_board(bo): for i in range(len(bo)): if i%3 == 0 and i!=0: print("---------------------") for j in range(len(bo[0])): if j%3 == 0 and j!=0: print(" | ", end ="") if j==8: print(bo[i][j]) else: print(str(bo[i][j]) + " ",end="") def find_empty(bo): for i in range(len(bo)): for j in range(len(bo[0])): if bo[i][j] == 0: return (i, j) return None def valid(bo, num, pos): for i in range(len(bo[0])):#checking row if bo[pos[0]][i] == num and pos[1]!= i: return False for j in range(len(bo)):#checking column if bo[i][pos[1]] == num and pos[0]!= i: return False box_x = pos[1]//3 box_y = pos[0]//3 for i in range(box_y*3, box_y*3 + 3): for j in range(box_x*3, box_x*3 + 3): if bo[i][j] == num and (i,j) != pos: return False return True def solve(bo): find = find_empty(bo) if not find: return True else: row, col = find for i in range(1,10): if valid(bo, i , (row,col)): bo[row][col] = i if solve(bo): return True bo[row][col]=0 return False print_board(board) solve(board) print("Solving") print_board(board) print("Solved")

**Thanks For Reading…**