-
Notifications
You must be signed in to change notification settings - Fork 0
/
DLXspls23.py
101 lines (89 loc) · 2.62 KB
/
DLXspls23.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
#!/usr/bin/env python3
# Author: Ali Assaf <[email protected]>
# Copyright: (C) 2010 Ali Assaf
# License: GNU General Public License <http://www.gnu.org/licenses/>
from itertools import product
def solve_sudoku(size, grid):
# """ An efficient Sudoku solver using Algorithm X.
R, C = size
N = R * C
X = ([("rc", rc) for rc in product(range(N), range(N))] +
[("rn", rn) for rn in product(range(N), range(1, N + 1))] +
[("cn", cn) for cn in product(range(N), range(1, N + 1))] +
[("bn", bn) for bn in product(range(N), range(1, N + 1))] +
[("dn", bn) for bn in product(range(N), range(1, N + 1))])
Y = dict()
for r, c, n in product(range(N), range(N), range(1, N + 1)):
b = (r // R) * R + (c // C) # a \times b Box number
d = (r // C) * C + (c // R) # b \times a Box number
Y[(r, c, n)] = [
("rc", (r, c)),
("rn", (r, n)),
("cn", (c, n)),
("bn", (b, n)),
("dn", (d, n))]
X, Y = exact_cover(X, Y)
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
def exact_cover(X, Y):
X = {j: set() for j in X}
for i, row in Y.items():
for j in row:
X[j].add(i)
return X, Y
def solve(X, Y, solution):
if not X:
yield list(solution)
else:
c = min(X, key=lambda c: len(X[c]))
for r in list(X[c]):
solution.append(r)
cols = select(X, Y, r)
for s in solve(X, Y, solution):
yield s
deselect(X, Y, r, cols)
solution.pop()
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
if __name__ == "__main__":
import doctest
doctest.testmod()
solutions = 0
a = 2
b = 3
n = a*b
grid = [
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[1,2,3,0,0,0],
[4,5,6,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0]
]
numOfSoltns = 0
for solutions in solve_sudoku((a,b),grid):
numOfSoltns += 1
for s in solutions:
print(s)
print('solution number', numOfSoltns)
print('')