# Sudoku Solver w/ Backtracking

### Part 1

Subscribe to Tech With Tim!

In part 1 of this Sudoku solver with python tutorial I explain how we are going to go about solving the problem and discuss the algorithm known as backtracking. Backtracking is simply reverting back to the previous step or solution as soon as we determine that our current solution cannot be continued into a complete one. We will use this principle of backtracking to implement the following algorithm.

Algorithm

Starting with an incomplete board:

1. Find some empty space
2. Attempt to place the digits 1-9 in that space
3. Check if that digit is valid in the current spot based on the current board
4.  a. If the digit is valid, recursively attempt to fill the board using steps 1-3.
b. If it is not valid, reset the square you just filled and go back to the previous step.
5. Once the board is full by the definition of this algorithm we have found a solution.

We will finish about half of the algorithm in part 1. In part 2 (look below) we will implement the entire algorithm.

### Part 1 Code

```board = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]

def print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")

for j in range(len(bo)):
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)):
if bo[i][j] == 0:
return (i, j)  # row, col

return None
```

### Part 2

Subscribe to Tech With Tim!

In part 2 of this tutorial we will finish the algorithm and continue to understand how it works by running through our code step by step. We will use a recursive function to implement the algorithm explained in part 1.

### Part 2 Code

```board = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]

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

def valid(bo, num, pos):
# Check row
for i in range(len(bo)):
if bo[pos][i] == num and pos != i:
return False

# Check column
for i in range(len(bo)):
if bo[i][pos] == num and pos != i:
return False

# Check box
box_x = pos // 3
box_y = pos // 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 print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")

for j in range(len(bo)):
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)):
if bo[i][j] == 0:
return (i, j)  # row, col

return None

print_board(board)
solve(board)
print("___________________")
print_board(board)
```

### Building the GUI

Subscribe to Tech With Tim!

### GUI Code

For this GUI to work it must be inside the same directory as the file called solver.py. You must also have pygame installed on your system. To learn how to download/install pygame watch this video.

### GUI.py

```# GUI.py
import pygame
from solver import solve, valid
import time
pygame.font.init()

class Grid:
board = [
[7, 8, 0, 4, 0, 0, 1, 2, 0],
[6, 0, 0, 0, 7, 5, 0, 0, 9],
[0, 0, 0, 6, 0, 1, 0, 7, 8],
[0, 0, 7, 0, 4, 0, 2, 6, 0],
[0, 0, 1, 0, 5, 0, 9, 3, 0],
[9, 0, 4, 0, 6, 0, 0, 0, 5],
[0, 7, 0, 3, 0, 0, 0, 1, 2],
[1, 2, 0, 0, 0, 7, 4, 0, 0],
[0, 4, 9, 2, 0, 6, 0, 0, 7]
]

def __init__(self, rows, cols, width, height):
self.rows = rows
self.cols = cols
self.cubes = [[Cube(self.board[i][j], i, j, width, height) for j in range(cols)] for i in range(rows)]
self.width = width
self.height = height
self.model = None
self.selected = None

def update_model(self):
self.model = [[self.cubes[i][j].value for j in range(self.cols)] for i in range(self.rows)]

def place(self, val):
row, col = self.selected
if self.cubes[row][col].value == 0:
self.cubes[row][col].set(val)
self.update_model()

if valid(self.model, val, (row,col)) and solve(self.model):
return True
else:
self.cubes[row][col].set(0)
self.cubes[row][col].set_temp(0)
self.update_model()
return False

def sketch(self, val):
row, col = self.selected
self.cubes[row][col].set_temp(val)

def draw(self, win):
# Draw Grid Lines
gap = self.width / 9
for i in range(self.rows+1):
if i % 3 == 0 and i != 0:
thick = 4
else:
thick = 1
pygame.draw.line(win, (0,0,0), (0, i*gap), (self.width, i*gap), thick)
pygame.draw.line(win, (0, 0, 0), (i * gap, 0), (i * gap, self.height), thick)

# Draw Cubes
for i in range(self.rows):
for j in range(self.cols):
self.cubes[i][j].draw(win)

def select(self, row, col):
# Reset all other
for i in range(self.rows):
for j in range(self.cols):
self.cubes[i][j].selected = False

self.cubes[row][col].selected = True
self.selected = (row, col)

def clear(self):
row, col = self.selected
if self.cubes[row][col].value == 0:
self.cubes[row][col].set_temp(0)

def click(self, pos):
"""
:param: pos
:return: (row, col)
"""
if pos < self.width and pos < self.height:
gap = self.width / 9
x = pos // gap
y = pos // gap
return (int(y),int(x))
else:
return None

def is_finished(self):
for i in range(self.rows):
for j in range(self.cols):
if self.cubes[i][j].value == 0:
return False
return True

class Cube:
rows = 9
cols = 9

def __init__(self, value, row, col, width ,height):
self.value = value
self.temp = 0
self.row = row
self.col = col
self.width = width
self.height = height
self.selected = False

def draw(self, win):
fnt = pygame.font.SysFont("comicsans", 40)

gap = self.width / 9
x = self.col * gap
y = self.row * gap

if self.temp != 0 and self.value == 0:
text = fnt.render(str(self.temp), 1, (128,128,128))
win.blit(text, (x+5, y+5))
elif not(self.value == 0):
text = fnt.render(str(self.value), 1, (0, 0, 0))
win.blit(text, (x + (gap/2 - text.get_width()/2), y + (gap/2 - text.get_height()/2)))

if self.selected:
pygame.draw.rect(win, (255,0,0), (x,y, gap ,gap), 3)

def set(self, val):
self.value = val

def set_temp(self, val):
self.temp = val

def redraw_window(win, board, time, strikes):
win.fill((255,255,255))
# Draw time
fnt = pygame.font.SysFont("comicsans", 40)
text = fnt.render("Time: " + format_time(time), 1, (0,0,0))
win.blit(text, (540 - 160, 560))
# Draw Strikes
text = fnt.render("X " * strikes, 1, (255, 0, 0))
win.blit(text, (20, 560))
# Draw grid and board
board.draw(win)

def format_time(secs):
sec = secs%60
minute = secs//60
hour = minute//60

mat = " " + str(minute) + ":" + str(sec)
return mat

def main():
win = pygame.display.set_mode((540,600))
pygame.display.set_caption("Sudoku")
board = Grid(9, 9, 540, 540)
key = None
run = True
start = time.time()
strikes = 0
while run:

play_time = round(time.time() - start)

for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_1:
key = 1
if event.key == pygame.K_2:
key = 2
if event.key == pygame.K_3:
key = 3
if event.key == pygame.K_4:
key = 4
if event.key == pygame.K_5:
key = 5
if event.key == pygame.K_6:
key = 6
if event.key == pygame.K_7:
key = 7
if event.key == pygame.K_8:
key = 8
if event.key == pygame.K_9:
key = 9
if event.key == pygame.K_DELETE:
board.clear()
key = None
if event.key == pygame.K_RETURN:
i, j = board.selected
if board.cubes[i][j].temp != 0:
if board.place(board.cubes[i][j].temp):
print("Success")
else:
print("Wrong")
strikes += 1
key = None

if board.is_finished():
print("Game over")
run = False

if event.type == pygame.MOUSEBUTTONDOWN:
pos = pygame.mouse.get_pos()
clicked = board.click(pos)
if clicked:
board.select(clicked, clicked)
key = None

if board.selected and key != None:
board.sketch(key)

redraw_window(win, board, play_time, strikes)
pygame.display.update()

main()
pygame.quit()
```

### solver.py

```# solver.py

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

def valid(bo, num, pos):
# Check row
for i in range(len(bo)):
if bo[pos][i] == num and pos != i:
return False

# Check column
for i in range(len(bo)):
if bo[i][pos] == num and pos != i:
return False

# Check box
box_x = pos // 3
box_y = pos // 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 print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")

for j in range(len(bo)):
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)):
if bo[i][j] == 0:
return (i, j)  # row, col

return None
```