Instructions
Requirements and Specifications
Source Code
"""## Load Puzzle"""
def load_puzzle(filename):
puzzle = []
with open(filename, 'r') as f:
data = f.readlines()
for line in data:
token_strings = line.split(" ")
row = map(int, token_strings)
token_ints = [i for i in row]
puzzle.append(token_ints)
return puzzle
"""## Display Puzzle"""
def display_puzzle(puzzle):
row_counter = 0
for idx, tokens in enumerate(puzzle):
if idx in [0, 3, 6]:
print('+-------+-------+-------+')
row = "| "
for e_idx, element in enumerate(tokens):
if element == 0:
row += '. '
else:
row += str(element) + " "
if e_idx in [2, 5, 8]:
row += '| '
print(row)
print('+-------+-------+-------+')
"""## Get Next"""
def get_next(row, col):
if col < 8:
return row, col+1
if col == 8 and row < 8:
return row+1, 0
if col == 8 and row == 8:
return None, None
"""## Copy Puzzle"""
def copy_puzzle(puzzle):
new_puzzle = []
for row in puzzle:
row_copy = row.copy()
new_puzzle.append(row_copy)
return new_puzzle
"""## Get Options"""
def get_options(puzzle, row, col):
if puzzle[row][col] > 0:
return None
else:
# get valid values
# Scan row first
used = []
for col_ in range(0, 9):
if puzzle[row][col_] != 0:
used.append(puzzle[row][col_])
# Scan column
for row_ in range(0, 9):
if puzzle[row_][col] != 0:
used.append(puzzle[row_][col])
# Now, scan block
start_row = 3*int(row/3)
start_col = 3*int(col/3)
for row_ in range(start_row, start_row+3):
for col_ in range(start_col, start_col+3):
if puzzle[row_][col_] != 0:
used.append(puzzle[row_][col_])
# Now, get all values that are not in the row or the column
options = []
for i in range(1, 10):
if i not in used:
options.append(i)
return options
"""## Solve"""
def solve(puzzle, row = 0, col = 0):
if puzzle[row][col] != 0: # cell is not blank
next_row, next_col = get_next(row,col)
if next_row is None:
return puzzle
else:
return solve(puzzle, next_row, next_col)
else: # cell is blank
options = get_options(puzzle, row, col)
if len(options) == 0: # options is empty
return None
else: # options is not empty
for digit in options:
new_puzzle = copy_puzzle(puzzle)
new_puzzle[row][col] = digit
result = solve(new_puzzle, row, col)
if result != None: # solution found
return result