Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Knuth's Dancing Links (DLX) - pretty fast solution in Clear category for Sudoku Solver by karlian
# original paper by Donald Knuth https://arxiv.org/pdf/cs/0011047.pdf
# sudoku paper by Jonathan Chu https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html
# also inspired by the dict based implementation of Ali Assaf https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
from functools import partialmethod
from itertools import product
from operator import attrgetter
class Node:
def __init__(self, data):
self.left = self.right = self.up = self.down = self
self.data, self.col = data, None
def insert_left(self, other):
other.right, other.left = self, self.left
self.left.right = self.left = other
def insert_up(self, other):
other.down, other.up = self, self.up
self.up.down = self.up = other
def remove_left_right(self):
self.left.right, self.right.left = self.right, self.left
def remove_up_down(self):
self.up.down, self.down.up = self.down, self.up
def iter(self, getter):
node = getter(self)
while node is not self:
yield node
node = getter(node)
iter_left = partialmethod(iter, attrgetter("left"))
iter_right = partialmethod(iter, attrgetter("right"))
iter_up = partialmethod(iter, attrgetter("up"))
iter_down = partialmethod(iter, attrgetter("down"))
class Column(Node):
def __init__(self, data):
super().__init__(data)
self.size = 0
def add_node(self, node):
node.col = self
self.size += 1
self.insert_up(node)
def cover(self):
self.remove_left_right()
for i in self.iter_down():
for j in i.iter_right():
j.col.size -= 1
j.remove_up_down()
def uncover(self):
for i in self.iter_up():
for j in i.iter_left():
j.col.size += 1
j.down.up = j.up.down = j
self.left.right = self.right.left = self
class Root(Node):
def __init__(self):
super().__init__("root")
self.columns = dict()
def find_or_create(self, data):
node = self.columns.get(data, None)
if not node:
node = self.columns[data] = Column(data)
self.insert_left(node)
return node
def search(self, *solution):
if self.right is self:
return solution
else:
col = min(self.iter_right(), key=attrgetter("size"))
col.cover()
for row in col.iter_down():
for j in row.iter_right():
j.col.cover()
if result := self.search(*solution, row.data):
return result
for j in row.iter_left():
j.col.uncover()
col.uncover()
R = C = 3
N = R * C
def columns(r, c, n):
b = r // R * R + c // C
return (("rc", r, c), ("rn", r, n), ("cn", c, n), ("bn", b, n))
def checkio(grid):
clues = {data
for r, row in enumerate(grid)
for c, n in enumerate(row)
if n
for data in columns(r, c, n)}
root = Root()
for r, c, n in product(range(N), range(N), range(1, N + 1)):
cols = columns(r, c, n)
if clues.isdisjoint(cols):
tmp = Node(None)
for data in cols:
col = root.find_or_create(data)
tmp.insert_left(node := Node((r, c, n)))
col.add_node(node)
tmp.remove_left_right()
for (r, c, n) in root.search(): grid[r][c] = n
return grid
July 19, 2022
Comments:
