-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdlx.py
150 lines (128 loc) · 4.53 KB
/
dlx.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
140
141
142
143
144
145
146
147
148
149
150
from math import inf
class Node(object):
def __init__(self, column, row):
self.column = column
self.row = row
self.up, self.down, self.left, self.right = self, self, self, self
class ColumnNode(Node):
def __init__(self, id):
Node.__init__(self, self, id)
self.row_count = 0
class DLX(object):
def __init__(self):
self.root = ColumnNode(0)
def create_matrix(self, grid_str):
"""Creates an exact cover matrix from a sudoku grid"""
root = self.root
cols = [root]
# Construct column headers as a doubly circular linked list
# We'll be storing all the column headers in a list for easy access
for i in range(324):
c = ColumnNode(i + 1)
c.right = root
c.left = root.left
root.left.right = c
root.left = c
cols.append(c)
# These help us find which constraint should be filled in
row_constraint = lambda x, k: 81 + (x // 9) * 9 + k
col_constraint = lambda x, k: 162 + (x % 9) * 9 + k
box_constraint = lambda x, k: 243 + (x // 27) * 27 + (x % 9) // 3 * 9 + k
row_num = lambda x, k: x * 9 + k
def _append_to_column(n):
"""Appends a row node at the end of a column"""
c = n.column
c.row_count += 1
n.down = c
n.up = c.up
c.up.down = n
c.up = n
def _create_links(x, k):
"""Creates links for a row"""
cell_node = Node(cols[x + 1], row_num(x, k))
row_node = Node(cols[row_constraint(x, k)], row_num(x, k))
col_node = Node(cols[col_constraint(x, k)], row_num(x, k))
box_node = Node(cols[box_constraint(x, k)], row_num(x, k))
# Link all the nodes into a single row
cell_node.right, cell_node.left = row_node, box_node
row_node.right, row_node.left = col_node, cell_node
col_node.right, col_node.left = box_node, row_node
box_node.right, box_node.left = cell_node, col_node
_append_to_column(cell_node)
_append_to_column(row_node)
_append_to_column(col_node)
_append_to_column(box_node)
for index, chr in enumerate(grid_str):
if chr == '.':
# Square is empty, add all possible values
for k in range(9):
_create_links(index, k + 1)
else:
_create_links(index, ord(chr) - 48)
def choose_least_column(self):
"""
We use the S heuristic to minimize branching factor
Returns the column with the least number of rows
"""
c = None
i = self.root.right
s = inf
while i != self.root:
if i.row_count < s:
c = i
s = i.row_count
i = i.right
return c
def cover(self, col):
"""Removes a column along with all rows that intersect said column"""
col.right.left = col.left
col.left.right = col.right
i = col.down
while i != col:
# Iterate through nodes in row and unlink them
j = i.right
while j != i:
j.down.up = j.up
j.up.down = j.down
j.column.row_count -= 1
j = j.right
i = i.down
def uncover(self, col):
"""Undo covering of a column"""
i = col.up
while i != col:
j = i.left
while j != i:
j.down.up = j
j.up.down = j
j.column.row_count += 1
j = j.left
i = i.up
col.right.left = col
col.left.right = col
def search(self, solution):
"""Search for a solution from a exact cover matrix"""
# No columns left, a solution is found
if self.root == self.root.right:
return solution, True
c = self.choose_least_column()
self.cover(c)
i = c.down
while i != c:
solution.append(i)
j = i.right
while j != i:
self.cover(j.column)
j = j.right
solution, found = self.search(solution)
if found:
return solution, True
i = solution.pop()
c = i.column
j = i.left
while j != i:
self.uncover(j.column)
j = j.left
i = i.down
self.uncover(c)
return solution, False