-
Notifications
You must be signed in to change notification settings - Fork 0
/
check_board.py
139 lines (118 loc) · 4.01 KB
/
check_board.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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
import copy as cp
c = 0
Plat = [
[2, 2, 1, 1, 1, 2, 2],
[2, 1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1],
[2, 1, 1, 1, 1, 1, 2],
[2, 2, 1, 1, 1, 2, 2],
]
Plat3 = [
[2, 2, 1, 1, 1, 2, 2],
[2, 2, 1, 1, 1, 2, 2],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1],
[2, 2, 1, 1, 1, 2, 2],
[2, 2, 1, 1, 1, 2, 2],
]
Plat2 = [
[2, 1, 1, 1, 2],
[1, 1, 1, 1, 1],
[1, 1, 1, 0, 1],
[1, 1, 1, 1, 1],
[2, 1, 1, 1, 2],
]
# Were using a CaleyTable to compute an invariant phi for the board.
# This allows to find potential candidates for solutions, although it does not prove that a solution exists,
# even among these candidates.
# This rule is known as the "rule of three".
# More about this on http://eternitygames.free.fr/Solitaire.html#La%20r%C3%A8gle%20de%20trois
CaleyTable = [
[0, 1, 2, 3],
[1, 0, 3, 2],
[2, 3, 0, 1],
[3, 2, 1, 0],
]
def phi(board):
phi = [0, 0]
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 1:
phi_ = phi_ij(i, j)
phi = add_phi(phi, phi_)
return phi
def phi_ij(i, j):
return [(i + j) % 3 + 1, (i - j) % 3 + 1]
def add_phi(phi1, phi2):
return [CaleyTable[phi1[0]][phi2[0]], CaleyTable[phi1[1]][phi2[1]]]
def full_board(board):
fullboard = cp.deepcopy(board)
for i in range(len(fullboard)):
for j in range(len(fullboard[i])):
if fullboard[i][j] == 0:
fullboard[i][j] = 1
return fullboard
def check_one_possible_solution(board):
phi_board = phi(board)
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 1:
if phi_board == phi_ij(i, j):
return True
return False
def check_all_possible_solutions(board):
fullboard = full_board(board)
phi_board = phi(fullboard)
coords = []
init_positions_phi = []
last_positions_phi = []
for i in range(len(fullboard)):
for j in range(len(fullboard[i])):
if fullboard[i][j] == 1:
coords.append([i, j])
# This is phi for a board with one missing marble at ij
init_positions_phi.append(add_phi(phi_board, phi_ij(i, j)))
# This is phi for a board with only one marble at ij
last_positions_phi.append(phi_ij(i, j))
for k, init_phi in enumerate(init_positions_phi):
write_file = False
coord = coords[k]
this_board = cp.deepcopy(fullboard)
this_board[coord[0]][coord[1]] = 0
file_content = "Starting board :\n"
for ligne in this_board:
for el in ligne:
if el == 2:
file_content += " "
if el == 1:
file_content += "0"
if el == 0:
file_content += "."
file_content += "\n"
file_content += "\nPossible endings :\n"
for l, last_phi in enumerate(last_positions_phi):
if init_phi == last_phi:
write_file = True
print("Starting Position {:d} with last position {:d}".format(k, l))
coord = coords[l]
this_board = cp.deepcopy(fullboard)
this_board[coord[0]][coord[1]] = 0
for ligne in this_board:
for el in ligne:
if el == 2:
file_content += " "
if el == 0: # we invert the board for end position
file_content += "0"
if el == 1:
file_content += "."
file_content += "\n"
file_content += "\n"
if write_file:
write_file = open("PotentialSolutions%d.txt" % (k), "w")
write_file.write(file_content)
write_file.close()
if __name__ == "__main__":
check_all_possible_solutions(Plat)