From: https://www.techwithtim.net/tutorials/python-programming/sudoku-solver-backtracking/
import pygame, time
pygame.font.init()
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):
for i in range(len(bo[0])): # Check row
if bo[pos[0]][i] == num and pos[1] != i:
return False
for i in range(len(bo)): # Check column
if bo[i][pos[1]] == num and pos[0] != i:
return False
box_x = pos[1] // 3 # Check box
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 print_boards(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) # row, col
return None
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):
gap = self.width / 9 # Draw Grid Lines
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)
for i in range(self.rows): # Draw Cubes
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):
if pos[0] < self.width and pos[1] < self.height:
gap = self.width / 9
x = pos[0] // gap
y = pos[1] // gap
return (int(y), int(x)) # return: (col, row)
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, cols = 9, 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))
fnt = pygame.font.SysFont("comicsans", 30) # Draw time
text = fnt.render("Time: " + format_time(time), 1, (0,0,0))
win.blit(text, (200, 560))
text = fnt.render("X " * strikes, 1, (255, 0, 0)) # Draw Strikes
win.blit(text, (20, 560))
board.draw(win) # Draw grid and board
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 49 <= event.key <= 57: # Checking for digits 1 - 9
key = event.key - 48
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[0], clicked[1])
key = None
if board.selected and key != None:
board.sketch(key)
redraw_window(win, board, play_time, strikes)
pygame.display.update()
main()
pygame.quit()
