-
Notifications
You must be signed in to change notification settings - Fork 2
/
backtracking_3x3_puzzle
95 lines (81 loc) · 2.47 KB
/
backtracking_3x3_puzzle
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import time
starttime = time.time()
ROWS = [576,216,36]
COLS = [64,72,972]
row_factors = set()
for n in ROWS:
for i in range(1,n):
if n % i == 0:
row_factors.add(i)
col_factors = set()
for n in COLS:
for i in range(1,n):
if n % i == 0:
col_factors.add(i)
NUMS = [n for n in row_factors if n in col_factors]
print(NUMS)
def row(board,n):
"""Returns values in row n of board"""
return board[3*n:3*n+3]
def col(board,n):
"""Returns values in column n of board"""
col_nums = [[0,3,6],
[1,4,7],
[2,5,8]]
return [board[x] for x in col_nums[n]]
def repeat(board):
"""Returns True if there is a repeat"""
for n in board:
if n != 'X':
if board.count(n) > 1:
return True
return False
def product(lista):
"""Returns the product of the items in a list"""
output = 1
for n in lista:
if n != 'X':
output *= n
return output
def print_board(board):
for i in range(3):
print("{} {} {}".format(row(board,i)[0],
row(board,i)[1],
row(board,i)[2]))
print() #blank line
def check_no_conflicts(board):
"""Returns True if there are no conflicts"""
if repeat(board):
return False
for i in range(3):
#check ROWS
thisrow = row(board,i)
if thisrow.count('X') == 0:
if product(thisrow) != ROWS[i]:
return False
#check columns
thiscol = col(board,i)
if thiscol.count('X') == 0:
if product(thiscol) != COLS[i]:
return False
return True
def solve(values,safe_up_to,size):
"""Return the solution as a list of values"""
solution = ['X']*size
def extend_solution(position):
for value in values:
solution[position] = value
#print_board(solution)
if safe_up_to(solution):
if position >= size-1 or extend_solution(position+1):
return solution
else: #backtrack
solution[position] = 'X'
if value == values[-1]:
solution[position-1] = 'X'
if position < size-1:
solution[position + 1] = 'X'
return None
return extend_solution(0)
print_board(solve(NUMS,check_no_conflicts,9))
print("Time(secs):",round(time.time() - starttime,1))