73 lines
1.8 KiB
Python
73 lines
1.8 KiB
Python
# This program solves a sudoku by backtracking and filling all possible spaces.
|
|
|
|
def solve(board):
|
|
empty = find_empty(board)
|
|
|
|
if empty == None:
|
|
return True
|
|
else:
|
|
x, y = empty
|
|
|
|
for i in range(1,10):
|
|
if check_validity(board, x, y, i):
|
|
board[y][x] = i
|
|
|
|
if solve(board):
|
|
return True
|
|
|
|
board[y][x] = 0
|
|
|
|
return False
|
|
|
|
# This function Prints a Sudoku Board
|
|
def printb(board):
|
|
for x in range(len(board)):
|
|
if x % 3 == 0:
|
|
print('-------------------------')
|
|
for y in range(len(board[x])):
|
|
if y % 3 == 0:
|
|
print('|', end=' ')
|
|
print(board[x][y], end=' ')
|
|
print('|')
|
|
print('-------------------------')
|
|
|
|
|
|
# This function checks if a passed number in a set of coordinates in valid.
|
|
def check_validity(board, x, y, num):
|
|
# Check horizontal
|
|
for i in range(len(board)):
|
|
if board[y][i] == num and x != i:
|
|
return False
|
|
|
|
# Check vertical
|
|
for i in range(len(board)):
|
|
if board[i][x] == num and y != i:
|
|
return False
|
|
|
|
# Check square
|
|
sqr_x = (x // 3) * 3
|
|
sqr_y = (y // 3) * 3
|
|
|
|
for i in range(sqr_y, sqr_y + 3):
|
|
for j in range(sqr_x, sqr_x + 3):
|
|
if board[i][j] == num and (i, j) != (y, x):
|
|
return False
|
|
|
|
return True
|
|
|
|
|
|
# This function finds the first empty square in the Sudoku.
|
|
def find_empty(board):
|
|
for y in range(len(board)):
|
|
for x in range(len(board)):
|
|
if board[y][x] == 0:
|
|
return x, y
|
|
return None
|
|
|
|
# printb(board)
|
|
# starttime = time.time()
|
|
# solve(board)
|
|
# print('\n--------------------------\n')
|
|
# printb(board)
|
|
# print('\nIt took us ' + str(round(time.time() - starttime)) + ' seconds to solve the sudoku.')
|