103 lines
2.7 KiB
Python
103 lines
2.7 KiB
Python
# Sudoku problems.
|
|
# The CSP.ac_3() and CSP.backtrack() methods need to be implemented
|
|
|
|
import sys
|
|
from io import StringIO
|
|
from time import time
|
|
|
|
from csp import CSP, alldiff
|
|
|
|
|
|
def print_solution(solution):
|
|
"""
|
|
Convert the representation of a Sudoku solution, as returned from
|
|
the method CSP.backtracking_search(), into a Sudoku board.
|
|
"""
|
|
for row in range(width):
|
|
for col in range(width):
|
|
print(solution[f"X{row+1}{col+1}"], end=" ")
|
|
if col == 2 or col == 5:
|
|
print("|", end=" ")
|
|
print("")
|
|
if row == 2 or row == 5:
|
|
print("------+-------+------")
|
|
|
|
|
|
# Choose Sudoku problem
|
|
grid = open(sys.argv[1] if len(sys.argv) > 1 else "sudoku_easy.txt").read().split()
|
|
|
|
width = 9
|
|
box_width = 3
|
|
|
|
domains = {}
|
|
for row in range(width):
|
|
for col in range(width):
|
|
if grid[row][col] == "0":
|
|
domains[f"X{row+1}{col+1}"] = set(range(1, 10))
|
|
else:
|
|
domains[f"X{row+1}{col+1}"] = {int(grid[row][col])}
|
|
|
|
edges = []
|
|
for row in range(width):
|
|
edges += alldiff([f"X{row+1}{col+1}" for col in range(width)])
|
|
for col in range(width):
|
|
edges += alldiff([f"X{row+1}{col+1}" for row in range(width)])
|
|
for box_row in range(box_width):
|
|
for box_col in range(box_width):
|
|
cells = []
|
|
edges += alldiff(
|
|
[
|
|
f"X{row+1}{col+1}"
|
|
for row in range(box_row * box_width, (box_row + 1) * box_width)
|
|
for col in range(box_col * box_width, (box_col + 1) * box_width)
|
|
]
|
|
)
|
|
|
|
csp = CSP(
|
|
variables=[f"X{row+1}{col+1}" for row in range(width) for col in range(width)],
|
|
domains=domains,
|
|
edges=edges,
|
|
)
|
|
|
|
# funny python code to hijack and redirect stdout
|
|
start_ac_3 = time()
|
|
print(csp.ac_3())
|
|
|
|
original_stdout = sys.stdout
|
|
sys.stdout = StringIO()
|
|
|
|
start_backtracking_search = time()
|
|
result = csp.backtracking_search()
|
|
end_time = time()
|
|
|
|
data = sys.stdout.getvalue().splitlines()
|
|
|
|
sys.stdout = original_stdout
|
|
|
|
print_solution(result)
|
|
|
|
number_of_failures = len([x for x in data if x == "i have failed"])
|
|
number_of_function_calls = len([x for x in data if x == "i have been called"])
|
|
print(
|
|
f"Backtrack failed {number_of_failures} times out of {number_of_function_calls} calls."
|
|
)
|
|
print(f"Running both AC-3 and backtracking search took {end_time - start_ac_3:.5f}")
|
|
print(
|
|
f"Running only backtracking search took {end_time - start_backtracking_search:.5f}"
|
|
)
|
|
|
|
|
|
# Expected output after implementing csp.ac_3() and csp.backtracking_search():
|
|
# True
|
|
# 7 8 4 | 9 3 2 | 1 5 6
|
|
# 6 1 9 | 4 8 5 | 3 2 7
|
|
# 2 3 5 | 1 7 6 | 4 8 9
|
|
# ------+-------+------
|
|
# 5 7 8 | 2 6 1 | 9 3 4
|
|
# 3 4 1 | 8 9 7 | 5 6 2
|
|
# 9 2 6 | 5 4 3 | 8 7 1
|
|
# ------+-------+------
|
|
# 4 5 3 | 7 2 9 | 6 1 8
|
|
# 8 6 2 | 3 1 4 | 7 9 5
|
|
# 1 9 7 | 6 5 8 | 2 4 3
|