Here is the description of Algorithm X from Wikipedia:
...is a recursive, nondeterministic, depth-first, brute-force algorithm that finds all solutions to the exact cover problem represented by a matrix A consisting of 0s and 1s.
It can be downloaded here.
# What is the matrix? It is a helper class
# for exact cover below.
class Matrix:
def __init__(self, list_of_lists):
self.m = [list_elt[:] for list_elt in list_of_lists]
self.unique = object()
def copy(self):
new = Matrix(self.m)
for r in new.m:
for i in range(len(r)):
if r[i] == self.unique:
r[i] = new.unique
return new
def delcol(self, i):
for r in self.m:
r[i] = self.unique
def delrow(self, i):
row = self.m[i]
for j in range(len(row)):
row[j] = self.unique
def empty(self):
for r in self.m:
for x in r:
if x != self.unique:
return False
return True
# Select first column with lowest number of 1s.
# Also, returns the number of 1s found in the
# column.
def selcol(self):
i = -1
s = -1
for colidx in range(len(self.m[0])):
colitems = [r[colidx] for r in self.m]
if all(x==self.unique for x in colitems):
continue
t = colitems.count(1)
if s == -1 or t < s:
s = t
i = colidx
return i, s
# == Algorithm X ======================================================
class ExactCover:
def X(self, matrix):
if matrix.empty():
return []
result = self.__X(matrix.copy())
if result:
all_answers = []
for answer in result:
all_answers.append([matrix.m[rowidx]
for rowidx in answer])
return all_answers
else:
return []
def __X(self, matrix):
# 1. Select 1st column with lowest
# number of 0s.
c, s = matrix.selcol()
if s == 0:
return []
# 2. Pick rows that have 1s in the
# above column.
possible_rows = [(i, r) for (i, r) in enumerate(matrix.m) if r[c] == 1]
random.shuffle(possible_rows)
answers = []
# 3. For each such row:
for rowidx, r in possible_rows:
new = matrix.copy()
for i, item in enumerate(r):
# - pick columns that have 1s
# in them
# 4. For each such col:
if item == 1:
for j, item2 in enumerate([r[i] for r in new.m]):
# - delete rows that have a 1
# in that column
if item2 == 1:
new.delrow(j)
# - delete that column
# [this was a bug before;
# it used to be above the
# for loop right after the
# "item == 1" expr]
new.delcol(i)
if new.empty():
answers.append([rowidx])
else:
# - recur on the sub-matrix
result = self.__X(new)
for x in result:
x.append(rowidx)
answers.append(x)
return answers
# == Tests ==========================================
def test_exact_cover():
e = [[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, 1, 1],
[0, 1, 0, 0, 0, 0, 1]]
m = Matrix(e)
res = ExactCover().X(m)
if res == [[[0, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 1, 0],
[1, 0, 0, 1, 0, 0, 0]]]:
print "test pass"
else:
print "test fail"