在上一篇文章中，我们通过改造了dancing link代码解出了aquarium游戏，并输出了正确答案。
但是之前的代码感觉有些慢，10*10的谜面都要跑24秒，而且感觉之前的dancing link代码有些不完善（存在重复查询问题）。这一篇文章介绍如何改良多值覆盖dancing link模板代码，还有如何在整体上优化这个游戏的解题流程。
之前的代码是从所有列中选择可能性最少的列进行突破，以减少查询宽度；但是在查询过程中发现了问题：之前查询过的较高占据值的行可能会再次被查询到，从而浪费不少时间。这里就需要在每个列的查询过程做额外处理：先从值最大的行开始消除，并且退出对这个列的遍历之前都不还原这些行。
之前遍历序列可能是这样：[1,2,3] [1,2,4] [1,3,2] [1,3,4] [1,4,2] [1,4,3]，现在的序列则是：[1,2,3] [1,2,4] [1,3,4] [2,3,4]，查询次数少了一些（别小看这少掉的2次·，反应到查询树里面影响可能显著，特别是最初的几层）
还有一些重要的优化：如果消除的行过多，导致最终能选的行总值无法满足要求，也要及时返回。为了随时随地查验总值，防止过度消除，在headerCell里面添加一个属性：xum_limit_num，并根据这个思路进行优化：
""" Implementation of Donald Knuth's Dancing Links Sparse Matrix as a circular doubly linked list. (http://arxiv.org/abs/cs/0011047) """ import random import numpy as np __author__ = "FunCfans" class CannotAddRowsError(Exception): pass # class EmptyDLMatrix(Exception): pass # class Cell: """ Inner cell, storing 4 pointers to neighbors, a pointer to the column header and the indexes associated. """ __slots__ = list("UDLRC") + ["indexes", "limit_num"] def __init__(self, limitNum=1): self.U = self.D = self.L = self.R = self self.C = None self.indexes = None self.limit_num = limitNum def __str__(self): return f"Node: {self.indexes}" def __repr__(self): return f"Cell[{self.indexes}]" class HeaderCell(Cell): """ Column Header cell, a special cell that stores also a name and a size member. """ __slots__ = ["size", "name", "is_first", "sum_limit_num"] def __init__(self, name, limitNum=1): super(HeaderCell, self).__init__(limitNum) self.size = 0 self.name = name self.is_first = False self.sum_limit_num = 0 class DancingLinksMatrix: """ Dancing Links sparse matrix implementation. It stores a circular doubly linked list of 1s, and another list of column headers. Every cell points to its upper, lower, left and right neighbors in a circular fashion. """ def __init__(self, columns): """ Creates a DL_Matrix. :param columns: it can be an integer or an iterable. If columns is an integer, columns columns are added to the matrix, named C0,...,CN where N = columns -1. If columns is an iterable, the number of columns and the names are deduced from the iterable, else TypeError is raised. The iterable may yield the names, or a tuple (name,primary). primary is a bool value that is True if the column is a primary one. If not specified, is assumed that the column is a primary one. :raises TypeError, if columns is not a number neither an iterable. """ self.header = HeaderCell("<H>") self.header.is_first = True self.rows = self.cols = 0 self.col_list = [] self._create_column_headers(columns) def _create_column_headers(self, columns): if isinstance(columns, int): columns = int(columns) column_names = ((f"C{i}", 1) for i in range(columns)) else: try: column_names = iter(columns) except TypeError: raise TypeError("Argument is not valid") prev = self.header # links every column in a for loop for name in column_names: primary = True if isinstance(name, tuple) or isinstance(name, list): name, limitNum = name else: limitNum = 1 cell = HeaderCell(name, limitNum) cell.indexes = (-1, self.cols) cell.is_first = False self.col_list.append(cell) if primary: prev.R = cell cell.L = prev prev = cell self.cols += 1 prev.R = self.header self.header.L = prev def add_sparse_row(self, row, already_sorted=False): """ Adds a sparse row to the matrix. The row is in format [ind_0, ..., ind_n] where 0 <= ind_i < dl_matrix.ncols. If called after end_add is executed, CannotAddRowsError is raised. :param row: a sequence of integers indicating the 1s in the row. :param already_sorted: True if the row is already sorted, default is False. Use it for performance optimization. :raises CannotAddRowsError if end_add was already called. """ if self.col_list is None: raise CannotAddRowsError() prev = None start = None if not already_sorted: row = sorted(row) cell = None for ind in row: if isinstance(ind, int): ind = (ind, 1) cell = Cell(ind[1]) cell.indexes = (self.rows, ind[0]) if prev: prev.R = cell cell.L = prev else: start = cell col = self.col_list[ind[0]] # link the cell with the previous one and with the right column # cells. last = col.U last.D = cell cell.U = last col.U = cell cell.D = col cell.C = col col.size += 1 prev = cell col.sum_limit_num += ind[1] start.L = cell cell.R = start self.rows += 1 def end_add(self): """ Called when there are no more rows to be inserted. Not strictly necessary, but it can save some memory. """ self.col_list = None def min_column(self): """ Returns the column header of the column with the minimum number of 1s. :return: A column header. :raises: EmptyDLMatrix if the matrix is empty. """ # noinspection PyUnresolvedReferences if self.header.R.is_first: raise EmptyDLMatrix() col_min = self.header.R for col in iterate_cell(self.header, 'R'): if not col.is_first and col.size < col_min.size: col_min = col return col_min def random_column(self): """ Returns a random column header. (The matrix header is never returned) :return: A column header. :raises: EmptyDLMatrix if the matrix is empty. """ col = self.header.R if col is self.header: raise EmptyDLMatrix() n = random.randint(0, self.cols - 1) for _ in range(n): col = col.R if col.is_first: col = col.R return col def __str__(self): names = [] m = np.zeros((self.rows, self.cols), dtype=np.uint8) rows, cols = set(), [] for col in iterate_cell(self.header, 'R'): cols.append(col.indexes[1]) # noinspection PyUnresolvedReferences names.append(col.name) for cell in iterate_cell(col, 'D'): ind = cell.indexes rows.add(ind[0]) m[ind] = 1 m = m[list(rows)][:, cols] return " ".join([", ".join(names), str(m)]) @staticmethod def coverRow(r, isadd=False): for j in iterate_cell(r, 'R'): if j.C.limit_num < j.limit_num: return False for j in iterate_cell(r, 'R'): j.D.U = j.U j.U.D = j.D j.C.size -= 1 j.C.sum_limit_num -= j.limit_num if isadd: j.C.limit_num -= j.limit_num return True @staticmethod def checkCover(c): subLimitNum = {} for i in iterate_cell(c, 'D'): for j in iterate_cell(i, 'R'): idx = j.indexes[1] if idx not in subLimitNum: subLimitNum[idx] = 0 subLimitNum[idx] += j.limit_num if j.C.sum_limit_num - subLimitNum[idx] < j.C.limit_num: return False return True @staticmethod def cover(c, isadd=False): """ Covers the column c by removing the 1s in the column and also all the rows connected to them. :param c: The column header of the column that has to be covered. """ # print("Cover column", c.name) c.R.L = c.L c.L.R = c.R for i in iterate_cell(c, 'D'): DancingLinksMatrix.coverRow(i, isadd) return True @staticmethod def uncoverRow(r, isadd=False): for j in iterate_cell(r, 'L'): j.C.sum_limit_num += j.limit_num j.C.size += 1 j.D.U = j.U.D = j if isadd: j.C.limit_num += j.limit_num return True @staticmethod def uncover(c, isadd=False): """ Uncovers the column c by readding the 1s in the column and also all the rows connected to them. :param c: The column header of the column that has to be uncovered. """ # print("Uncover column", c.name) for i in iterate_cell(c, 'U'): DancingLinksMatrix.uncoverRow(i, isadd) c.R.L = c.L.R = c def iterate_cell(cell, direction): cur = getattr(cell, direction) while cur is not cell: yield cur cur = getattr(cur, direction) # TODO to be completed class MatrixDisplayer: def __init__(self, matrix): dic = {} for col in iterate_cell(matrix.header, 'R'): dic[col.indexes] = col for col in iterate_cell(matrix.header, 'R'): first = col.D dic[first.indexes] = first for cell in iterate_cell(first, 'D'): if cell is not col: dic[cell.indexes] = cell self.dic = dic self.rows = matrix.rows self.cols = matrix.cols def print_matrix(self): m = {} for i in range(-1, self.rows): for j in range(0, self.cols): cell = self.dic.get((i, j)) if cell: if i == -1: m[0, 2 * j] = cell.name+','+str(cell.limit_num) else: m[2 * (i + 1), 2 * j] = "X"+','+str(cell.limit_num) for i in range(-1, self.rows * 2): for j in range(0, self.cols * 2): print(m.get((i, j), " "), end="") print() if __name__ == "__main__": def from_dense(row): return [i for i, el in enumerate(row) if el] r = [from_dense([1, 0, 0, 1, 0, 0, 1]), from_dense([1, 0, 0, 1, 0, 0, 0]), from_dense([0, 0, 0, 1, 1, 0, 1]), from_dense([0, 0, 1, 0, 1, 1, 0]), from_dense([0, 1, 1, 0, 0, 1, 1]), from_dense([0, 1, 0, 0, 0, 0, 1])] d = DancingLinksMatrix("1234567") for row in r: d.add_sparse_row(row, already_sorted=True) d.end_add() p = MatrixDisplayer(d) p.print_matrix() # print(d.rows) # print(d.cols) # print(d) mc = d.min_column() # print(mc) d.cover(mc) # print(d) p.print_matrix()
还有这个：
""" Implementation of Donald Knuth's Algorithm X (http://arxiv.org/abs/cs/0011047). """ from dlmatrix import DancingLinksMatrix, iterate_cell, MatrixDisplayer import string __author__ = 'FunCfans' testRow = [0 ,62 ,63 ,25 ,37 ,52 ,32 ,54 ,40 ,17 ,34 ,19 ,24 ,13] class AlgorithmX: """Callable object implementing the Algorithm X.""" def __init__(self, matrix, callback, choose_min=True): """ Creates an Algorithm_X object that solves the problem encoded in matrix. :param matrix: The DL_Matrix instance. :param callback: The callback called on every solution. callback has to be a function receiving a dict argument {row_index: linked list of the row}, and can return a bool value. The solver keeps going on until the callback returns a True value. :param choose_min: If True, the column with the minimum number of 1s is chosen at each iteration, if False a random column is chosen. """ self.sol_dict = {} self.stop = False self.matrix = matrix self.callback = callback self.choose_min = choose_min self.deduce_cnt = 0 self.depth = 0 self.last_matrix = None self.delta_file = None def __call__(self): """Starts the search.""" #self.delta_file = open('delta_matrix.txt','w',encoding='utf-8') #self._print(self.matrix.header, 'start') self._search(0) #self.delta_file.close() def _print(self, currrow, op): self.deduce_cnt += 1 f = open('step/' + 'step%04d_' % (self.deduce_cnt) + op + '_' + str(currrow.indexes) + '_depth%d.txt'%(self.depth),'w',encoding='utf-8') printrow = {} rowcontent = '' content = 'curr ' + op + ' row : ' + str(currrow.indexes) + ' ' content = '' for col in iterate_cell(self.matrix.header, 'R'): content += 'col name : '+col.name+' col limit : ' + str(col.limit_num) for row in iterate_cell(col, 'D'): content += ' ' + str((row.indexes[0],row.limit_num)) + ',' printrow[row.indexes[0]] = row content += ' ' content += ' ' for k,v in printrow.items(): content += 'row %d : '%(k) + str((v.limit_num, v.indexes[1])) + '-->' qv = v.R while(qv != v): content += str((qv.limit_num, qv.indexes[1])) + '-->' qv = qv.R content += str((qv.limit_num, qv.indexes[1])) + ' ' f.write(content) f.close() if self.last_matrix == None: self.last_matrix = {} for col in iterate_cell(self.matrix.header, 'R'): self.last_matrix[(col.name, col.indexes[0])] = collist = set() for row in iterate_cell(col, 'D'): collist.add(row.indexes[0]) else: curr_matrix = {} for col in iterate_cell(self.matrix.header, 'R'): curr_matrix[(col.name, col.indexes[0])] = collist = set() for row in iterate_cell(col, 'D'): collist.add(row.indexes[0]) add_col = set() addv = set(curr_matrix.keys()).difference(set(self.last_matrix.keys())) if len(addv) > 0: self.delta_file.write('add_col : '+str(addv) + ' ') delv = set(self.last_matrix.keys()).difference(set(curr_matrix.keys())) if len(delv) > 0: self.delta_file.write('delete_col : '+str(delv) + ' ') for k,v in curr_matrix.items(): if k not in self.last_matrix:continue addv = v.difference(self.last_matrix[k]) if len(addv) > 0: self.delta_file.write('add_col_'+str(k)+' : '+str(addv)) self.delta_file.write(' ') for k,v in self.last_matrix.items(): if k not in curr_matrix:continue delv = self.last_matrix[k].difference(v) if len(delv) > 0: self.delta_file.write('delete_col_'+str(k)+' : '+str(delv)) self.delta_file.write(' ') self.delta_file.write(' ') self.last_matrix = curr_matrix def _search(self, k): # print(f"Size: {k}") # k is depth # print(f"Solution: {self.sol_dict}") # print("Matrix:") # print(self.matrix) if self.matrix.header.R == self.matrix.header: # matrix is empty, solution found if self.callback(self._create_sol(k)): self.stop = True return if self.choose_min: col = self.matrix.min_column() else: col = self.matrix.random_column() # cover column col # row = col.D rows = [] for row in iterate_cell(col, 'D'): rows.append(row) rows.sort(key=lambda x:x.limit_num,reverse=True) self.depth += 1 for row in rows: if col.limit_num < row.limit_num:continue if col.sum_limit_num < col.limit_num:break isValid = True for j in iterate_cell(row, 'R'): if j.C.limit_num < j.limit_num: isValid = False break if not isValid: continue self.sol_dict[k] = row col.sum_limit_num -= row.limit_num col.limit_num -= row.limit_num row.D.U = row.U row.U.D = row.D col.size -= 1 if col.limit_num == 0: self.matrix.cover(col) for j in iterate_cell(row, 'R'): j.C.sum_limit_num -= j.limit_num j.C.limit_num -= j.limit_num j.D.U = j.U j.U.D = j.D j.C.size -= 1 if j.C.limit_num == 0: self.matrix.cover(j.C) execYou = True for j in iterate_cell(self.matrix.header, 'R'): if j.limit_num > j.sum_limit_num: execYou = False break if execYou: self._search(k + 1) if self.stop: return for j in iterate_cell(row, 'L'): if j.C.limit_num == 0: self.matrix.uncover(j.C) j.C.limit_num += j.limit_num if col.limit_num == 0: self.matrix.uncover(col) col.limit_num += row.limit_num del self.sol_dict[k] # uncover columns for row in rows[::-1]: for j in iterate_cell(row, 'L'): j.C.size += 1 j.D.U = j.U.D = j j.C.sum_limit_num += j.limit_num col.size += 1 row.D.U = row.U.D = row col.sum_limit_num += row.limit_num self.depth -= 1 # def _create_sol(self, k): # creates a solution from the inner dict sol = {} for key, row in self.sol_dict.items(): if key >= k: continue tmp_list = [row.C.name] tmp_list.extend(r.C.name for r in iterate_cell(row, 'R')) sol[row.indexes[0]] = tmp_list return sol # def main(): from_dense = (lambda row:[i for i, el in enumerate(row) if el]) rows = [from_dense([0, 0, 1, 0, 1, 1, 0]), from_dense([1, 0, 0, 1, 0, 0, 1]), from_dense([0, 1, 1, 0, 0, 1, 0]), from_dense([1, 0, 0, 1, 0, 0, 0]), from_dense([0, 1, 0, 0, 0, 0, 1]), from_dense([0, 0, 0, 1, 1, 0, 1])] size = max(max(rows, key=max)) + 1 d = DancingLinksMatrix(string.ascii_uppercase[:size]) for row in rows: d.add_sparse_row(row, already_sorted=True) AlgorithmX(d, print)() # if __name__ == "__main__": main()
利用这个解上一篇文章里面提到的10*10 easy，ID为69,467的谜面，运行时间为16秒。这说明了这个优化有效果。
但是，从原理上来讲，这个解法只是锦上添花而已。重要的是事前无效解的裁剪。
这道题目有这俩要求：
1.水箱内同高度的方格状态必须一致；
2.水箱内的方格必须自底向上填满。
就是说在指定数量条件下，还要满足这些条件。可以利用这些条件反应到单行中的所有可能性，初步排除错误解：
1.水箱内同高度的方格状态必须一致。这意味着某些占据长度过长的水箱段必须涂上去：
比如如下阵型：（下面水箱编号是0,0,0,0,1,1,1,2,2,3）
图1
可以涂上这种阵型：
图2
也可以这样涂：
图3
但是无论怎么涂，最左边的那4格都必须涂上（如果所有的阵型固定点都是白色，则亦可判定不可填涂），可以将最终阵型的对应位置填上；
这里最左边必须涂的原理还不止是这个：这里有10格，限制数量是7，如果去掉了严格大于(10-7)=3的水箱段，其他的水箱段加起来也达不到条件。
也有那种水箱占宽超过限制数量的：（下面水箱编号是0,0,0,0,0,1,1,1,2,2,2,2,2,3,3）
图4
像这种，除了最右边的1个水箱段，其他3个水箱段都要排除。
2.水箱内的方格必须自底向上填满，这意味着某些方格可以预先确定。与横段不同，竖段无需通过暴力搜索找到必经之路
看下栗子：（自底向上是8个0，5个1，2个2）
图5
如果把最下段去掉，其他段加起来也不够限制，因此下段至少需要加一些水到最底下。那要加多少格水呢，答案当然是9-(15-8)=2
再看以下栗子：（自底向上是5个0，3个1，5个2，2个3）
图6
可以看出，所有段严格大于2的段，上方都要用不到的区域，比如最下段，5个方格，最上面5-2=3个是用不了的。
初期阵型优化完毕之后再执行操作，可以减少许多不必要的搜索。
代码如下：
""" dominosa solver using Dancing Links. """ from functools import reduce from dlmatrix import DancingLinksMatrix from alg_x import AlgorithmX import math import time import copy deepcopy = copy.deepcopy __author__ = 'Funcfans' chess = [] valid = [] limits = [] presum = [] occupy = [] heights = [] currheights = [] heightIdxs = [] heightRange = [] haveBlock = {} rowsize = 0 maxnum = 0 def insertToStr(origin, i, j, value): if(origin[i][j] != '+'): origin[i] = origin[i][:j] + value + origin[i][j+1:] # def printAnswer(): subSubImg = ' ' * rowsize solImg = reduce(lambda a,b:a+' '+b,[subSubImg] * rowsize) blockheight = [0] * maxnum startHeight = {} for i in range(rowsize)[::-1]: for j in range(rowsize): if valid[i][j] == -1: chess[i][j] = -1 if valid[i][j] == 1: continue if chess[i][j] not in startHeight: startHeight[chess[i][j]] = i if startHeight[chess[i][j]] - blockheight[chess[i][j]] + 1 > i: chess[i][j] = -1 subSubImg = '-'.join(['+'] * (rowsize+1)) for i in range(rowsize): print(subSubImg) print('|',end='') for j in range(rowsize): if chess[i][j] == -1: print(' |',end='') else: print('*|',end='') print('') print(subSubImg) # def get_names(maxnum): cnt = 0 for i in range(maxnum): yield f'B({i})' # block cnt += 1 # base = maxnum presum.append([]) for i,limit in enumerate(limits[0]): presum[0].append(base) if limit != 0: yield (f'H({i},{limit})', limit) base += 1 # presum.append([]) for i,limit in enumerate(limits[1]): presum[1].append(base) if limit != 0: yield (f'V({i},{limit})', limit) base += 1 # def compute_row(value, maxnum): row = [] row.append(value) for d in range(2): for i,li in enumerate(occupy[d][value]): if li == 0:continue if li > limits[d][i]:return None row.append((presum[d][i],li)) return row # class PrintFirstSol: def __init__(self, r, c): self.r = r self.c = c def __call__(self, sol): subSubImg = ' ' * rowsize solImg = reduce(lambda a,b:a+' '+b,[subSubImg] * rowsize) blockheight = [0] * maxnum startHeight = [-1] * maxnum reverseBlock = {} for k,v in haveBlock.items(): reverseBlock[v] = k for k,v in sol.items(): v.sort() v[0] = 'B(' + str(reverseBlock[int(v[0].replace('B(','').replace(')',''))]) + ')' blockheight[heights[k][0]] = heights[k][1] # # for i in range(rowsize)[::-1]: for j in range(rowsize): if valid[i][j] == 1: continue if valid[i][j] == -1: chess[i][j] = -1 continue if startHeight[chess[i][j]] == -1: startHeight[chess[i][j]] = i if startHeight[chess[i][j]] - blockheight[chess[i][j]] + 1 > i: chess[i][j] = -1 subSubImg = '-'.join(['+'] * (rowsize+1)) for i in range(rowsize): print(subSubImg) print('|',end='') for j in range(rowsize): if valid[i][j] == 1: print('*|',end='') elif chess[i][j] == -1: print(' |',end='') else: print('*|',end='') print('') print(subSubImg) return True # allow = 0 def tryHorizontal(rowNum, startPos, subValid): have = {} totalvalid = rowsize totallimit = limits[0][rowNum] for i in range(rowsize)[::-1]: if valid[rowNum][i] != 0: totalvalid -= 1 if valid[rowNum][i] == 1: totallimit -= 1 continue value = chess[rowNum][i] if value not in have: have[value] = [i] else: have[value].append(i) items = [] for k,v in have.items(): if len(v) > totallimit: for j in v: subValid[j] = -1 totalvalid -= len(v) else: items.append((k, v)) items.sort(key=lambda a:len(a[1]),reverse=True) for i in items: v = i[1] if len(v) > totallimit: for j in v: subValid[j] = -1 totalvalid -= len(v) del items[items.index(i)] elif len(v) > totalvalid - totallimit: for j in v: subValid[j] = 1 totalvalid -= len(v) totallimit -= len(v) del items[items.index(i)] for i in range(2**len(items)): tryValid = [0] * rowsize mylimit = 0 for j in range(len(items)): if (i // (2**j)) % 2 == 1: for k in items[j][1]: tryValid[k] = 1 mylimit += len(items[j][1]) else: for k in items[j][1]: tryValid[k] = -1 if mylimit == totallimit: for j in range(rowsize): if tryValid[j] == 0:continue elif subValid[j] == -2:continue elif subValid[j] == 0:subValid[j] = tryValid[j] elif subValid[j] != tryValid[j]:subValid[j] = -2 return subValid # def fill(): isChange = False for i in range(rowsize): for checkValue in (-1,1): checkList = valid[i] if checkValue == -1: youlimit = limits[0][i] else: youlimit = rowsize - limits[0][i] if checkList.count(-checkValue) == youlimit: for j in range(rowsize): if valid[i][j] != -checkValue: valid[i][j] = checkValue if valid[i][j] != checkValue: isChange = True # checkList = list(map(lambda q:q[i], valid)) if checkValue == -1: youlimit = limits[1][i] else: youlimit = rowsize - limits[1][i] if checkList.count(-checkValue) == youlimit: for j in range(rowsize): if valid[j][i] != -checkValue: valid[j][i] = checkValue if valid[j][i] != checkValue: isChange = True # # return isChange # def tryVertical(colNum, startPos, subValid): have = {} totalvalid = rowsize totallimit = limits[1][colNum] for i in range(rowsize)[::-1]: if valid[i][colNum] != 0: totalvalid -= 1 if valid[i][colNum] == 1: totallimit -= 1 continue value = chess[i][colNum] if value not in have: have[value] = [i] else: have[value].append(i) for k,v in have.items(): for i in v[totallimit:]: subValid[i] = -1 if totallimit-totalvalid+len(v) > 0: for i in v[:totallimit-totalvalid+len(v)]: subValid[i] = 1 return subValid # def fill_up_down(blockNum, rowNum, value): #print('blockNum :',blockNum,'rowNum :',rowNum,'value :',value) queryCnts = range(rowNum+1)[::-1] if value == -1 else range(rowNum, rowsize) for k in queryCnts: isContinue = False for l in range(rowsize): if blockNum != chess[k][l]:continue if valid[k][l] == value:break else: valid[k][l] = value retry = True if value == -1: if heightRange[blockNum][0] < k: heightRange[blockNum][0] = k else: if heightRange[blockNum][1] > k: heightRange[blockNum][1] = k # def trySolve(): retry = True while retry: retry = False for i in range(rowsize): resultSet = tryHorizontal(i, 0, [0] * rowsize) ''' print('limit num :',limits[0][i]) print('resultSet :',resultSet) print('hori valid :',valid[i]) print('hori chess :',chess[i]) ''' for j in range(rowsize): blockNum = chess[i][j] if resultSet[j] in (1,-1): if valid[i][j] == resultSet[j]:continue fill_up_down(blockNum, i, resultSet[j]) retry = True for i in range(rowsize): resultSet = tryVertical(i, rowsize-1, [0] * rowsize) for j in range(rowsize): blockNum = chess[j][i] if resultSet[j] in (1,-1): if valid[j][i] == resultSet[j]:continue fill_up_down(blockNum, j, resultSet[j]) retry = True if not retry:retry = fill() #print('------') # ''' for i in range(rowsize): for j in range(rowsize): if valid[i][j] == -1: print('X',end='') elif valid[i][j] == 0: print(' ',end='') else: print('*',end='') print() ''' # def main(fileName='aquarium69,467_3.txt'): currheights.clear() heights.clear() heightIdxs.clear() heightRange.clear() haveBlock.clear() start = time.time() with open(fileName,'r') as f: chessStr = f.read() rowStrs = chessStr.split(' ') global rowsize, maxnum rowsize = len(rowStrs) - 2 colSize = len(rowStrs[0].split(' ')) maxnum = 0 for rowStr in rowStrs[:-2]: row = [] validRow = [] for colStr in rowStr.split(' '): maxnum = maxnum if int(colStr) < maxnum else int(colStr) row.append(int(colStr)) validRow.append(0) chess.append(row) valid.append(validRow) #print(chess) list(map(lambda a:int(a),rowStrs[-1].split(' '))) limits.append(list(map(lambda a:int(a),rowStrs[-2].split(' ')))) limits.append(list(map(lambda a:int(a),rowStrs[-1].split(' ')))) maxnum += 1 for _ in range(maxnum):heightRange.append([-1,rowsize]) occupy.append([[0 for ___ in range(rowsize)] for __ in range(maxnum)]) occupy.append([[0 for ___ in range(rowsize)] for __ in range(maxnum)]) rowidx = 0 trySolve() isSolve = True for i in range(rowsize): for j in range(rowsize): if valid[i][j] == 0: isSolve = False if valid[i][j] == 1: limits[0][i] -= 1 limits[1][j] -= 1 if isSolve: printAnswer() end = time.time() print('the DLX runtime is : ' + str(end-start) + 's') return #print(presum) startIdx = 0 for i in range(rowsize): for j in range(rowsize): if valid[i][j] == 0: if chess[i][j] not in haveBlock: haveBlock[chess[i][j]] = startIdx chess[i][j] = startIdx startIdx += 1 else: chess[i][j] = haveBlock[chess[i][j]] #print(haveBlock) d = DancingLinksMatrix(get_names(startIdx)) for i in range(maxnum): currheights.append(0) heightIdxs.append([]) for i in haveBlock.values(): row = compute_row(i, startIdx) #print('row :', row) d.add_sparse_row(row, already_sorted=True) heightIdxs[i].append(rowidx) heights.append((i, 0)) rowidx += 1 currheights[i] += 1 for i,row in list(enumerate(chess))[::-1]: used = set() for j,col in enumerate(row): if valid[i][j] != 0:continue used.add(col) occupy[0][col][i] += 1 occupy[1][col][j] += 1 for col in used: row = compute_row(col, maxnum)# or i <= heightRange[col][0] or i >= heightRange[col][1] #print('row :', row) heightIdxs[col].append(rowidx) heights.append((col, currheights[col])) d.add_sparse_row(row, already_sorted=True) rowidx += 1 currheights[col] += 1 #print('heightRange :', heightRange) #print('heightIdxs :', heightIdxs) print('rowidx :', rowidx) d.end_add() p = PrintFirstSol(rowsize, colSize) AlgorithmX(d, p)() end = time.time() print('the DLX runtime is : ' + str(end-start) + 's') if __name__ == "__main__": #main('aquarium2,680,806_8.txt') #main('aquarium5,434,697_7.txt') #main('aquariumSpecial Daily 17-12-2019_9.txt') main()
运行10*10 easy，ID为69,467的谜面，时间为0.005000591278076172秒，效果显著！
运行15*15 hard，ID为5,434,697的谜面，运行结果：
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | |*|*|*|*|*|*|*|*| | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | |*|*|*|*| | | | | |*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | |*|*|*|*| | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*|*|*| | | |*|*|*|*|*|*|*|*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |*| | | |*|*| |*|*|*|*| | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | |*|*|*|*|*|*|*|*|*|*|*| | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| |*|*| |*|*|*|*|*|*|*|*|*| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*|*|*|*|*| | |*|*|*|*|*|*|*| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*|*| |*|*|*| |*|*|*|*|*|*|*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*|*|*|*|*|*|*|*|*| | |*|*|*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*|*|*|*|*|*|*|*|*|*|*|*| |*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | |*| |*|*|*|*|*|*|*|*|*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | |*|*| | |*|*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| | | | |*|*| |*| |*|*|*|*|*| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |*| | | | | | |*| | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ the DLX runtime is : 0.0890049934387207s
把答案填入对应谜面：
图7.只要掌握了有效的优化技巧，就算是高难谜面也解给你看
大功告成！