使用算法X在Python/numba中实现的exact cover

Donald Knuth的Dancing Links算法X在Python / numba中的实现

用法

pip install exact_cover_py

from exact_cover_py import exact_covers

problem = np.array([
        [1, 0, 0, 1, 0, 0, 1],
        [1, 0, 0, 1, 0, 0, 0],  # <--
        [0, 0, 0, 1, 1, 0, 1],
        [0, 0, 1, 0, 1, 1, 0],  # <--
        [0, 1, 1, 0, 0, 0, 1],
        [0, 1, 1, 0, 0, 1, 1],  # <--
        [0, 1, 0, 0, 0, 0, 1],
   ])

# exact_covers returns a generator of solutions

# one solution
print(next(exact_covers(problem)))
[1, 5, 3]

# all solutions
print(list(exact_covers(problem)))
[[1, 5, 3]]

# number of solutions
def mylen(iterable):
    return sum(map(lambda x: 1, iterable))

print(mylen(exact_covers(problem)))
2