-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLatin.py
68 lines (58 loc) · 1.71 KB
/
Latin.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
from itertools import product
from AlgorithmX import *
def solve_square(grid):
"""
A Latin Squares solver using Algorithm X.
:param grid:
:return:
"""
rows, columns = len(grid), len(grid[0])
N = rows
'''X is our universe - as a list'''
X = ([("rc", rc) for rc in product(range(N), range(N))] + # row, column; coordinates for the grid
[("rn", rn) for rn in product(range(N), range(1, N + 1))] + # 1 - 9 for each row (row_index, number)
[("cn", cn) for cn in product(range(N), range(1, N + 1))]) # 1 - 9 for each column (column_index, number)
print("X", X)
Y = dict()
'''
Y separates our universe into subsets
where (row, column, number) covers
- (row, column)
- (row_index, number)
- (column_index, number)
'''
for r, c, n in product(range(N), range(N), range(1, N + 1)):
Y[(r, c, n)] = [
("rc", (r, c)),
("rn", (r, n)),
("cn", (c, n))]
print("Y", Y)
X, Y = exact_cover(X, Y)
print("X", X)
print("Y", Y)
'''Select the known elements of the puzzle grid'''
for i, row in enumerate(grid):
for j, n in enumerate(row):
if n:
select(X, Y, (i, j, n))
for solution in solve(X, Y, []):
for (r, c, n) in solution:
grid[r][c] = n
yield grid
if __name__ == "__main__":
puzzle = [
[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1]]
for sol in solve_square(puzzle):
for line in sol:
print(line)
print()
"""
[1, 2, 3, 4]
[2, 1, 4, 3]
[3, 4, 1, 2]
[4, 3, 2, 1]
"""