-
Notifications
You must be signed in to change notification settings - Fork 0
/
nqueens csp problem.py
68 lines (51 loc) · 2.22 KB
/
nqueens csp problem.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from simpleai.search import CspProblem, backtrack, MOST_CONSTRAINED_VARIABLE, HIGHEST_DEGREE_VARIABLE, LEAST_CONSTRAINING_VALUE
import itertools
import time
N = int(input("Enter N: "))
variables_list = []
for i in range(1,N + 1):
variables_list.append(f"Q{i}")
variables = tuple(variables_list)
domains = dict((v, list(range(1, N + 1))) for v in variables)
combinations = list(itertools.combinations(variables,2))
def not_attacking(variables, values):
column_difference = abs(int(variables[0][1]) - int(variables[1][1]))
row_difference = abs(values[0] - values[1])
if(column_difference == row_difference): #diagonal attack
return False
if(values[0] == values[1]): #same row
return False
return True
constraints = []
for pair in combinations:
constraints.append((pair, not_attacking))
my_problem = CspProblem(variables, domains, constraints)
print("Default")
start = time.perf_counter()
print(backtrack(my_problem))
print(f"Time elapsed: {(time.perf_counter() - start):0.4f} seconds")
print()
print("Most constrained variable")
start = time.perf_counter()
print(backtrack(my_problem, variable_heuristic=MOST_CONSTRAINED_VARIABLE))
print(f"Time elapsed: {(time.perf_counter() - start):0.4f} seconds")
print()
print("Highest degree variable")
start = time.perf_counter()
print(backtrack(my_problem, variable_heuristic=HIGHEST_DEGREE_VARIABLE))
print(f"Time elapsed: {(time.perf_counter() - start):0.4f} seconds")
print()
print("Least constraining value")
start = time.perf_counter()
print(backtrack(my_problem, value_heuristic=LEAST_CONSTRAINING_VALUE))
print(f"Time elapsed: {(time.perf_counter() - start):0.4f} seconds")
print()
print("Most constrained variable + Least constraining value")
start = time.perf_counter()
print(backtrack(my_problem, variable_heuristic=MOST_CONSTRAINED_VARIABLE, value_heuristic=LEAST_CONSTRAINING_VALUE))
print(f"Time elapsed: {(time.perf_counter() - start):0.4f} seconds")
print()
print("Highest degree variable + Least constraining value")
start = time.perf_counter()
print(backtrack(my_problem, variable_heuristic=HIGHEST_DEGREE_VARIABLE, value_heuristic=LEAST_CONSTRAINING_VALUE))
print(f"Time elapsed: {(time.perf_counter() - start):0.4f} seconds")