Nonograms

题目

Around 1994, a certain kind of puzzles was very popular in England. The "Sunday Telegraph" newspaper wrote: "Nonograms are puzzles from Japan and are currently published each week only in The Sunday Telegraph. Simply use your logic and skill to complete the grid and reveal a picture or diagram." As a Prolog programmer, you are in a better situation: you can have your computer do the work!

The puzzle goes like this: Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths.

Problem statement: Solution:

      |_|_|_|_|_|_|_|_| 3         |_|X|X|X|_|_|_|_| 3           
      |_|_|_|_|_|_|_|_| 2 1       |X|X|_|X|_|_|_|_| 2 1         
      |_|_|_|_|_|_|_|_| 3 2       |_|X|X|X|_|_|X|X| 3 2         
      |_|_|_|_|_|_|_|_| 2 2       |_|_|X|X|_|_|X|X| 2 2         
      |_|_|_|_|_|_|_|_| 6         |_|_|X|X|X|X|X|X| 6           
      |_|_|_|_|_|_|_|_| 1 5       |X|_|X|X|X|X|X|_| 1 5         
      |_|_|_|_|_|_|_|_| 6         |X|X|X|X|X|X|_|_| 6           
      |_|_|_|_|_|_|_|_| 1         |_|_|_|_|X|_|_|_| 1           
      |_|_|_|_|_|_|_|_| 2         |_|_|_|X|X|_|_|_| 2           
       1 3 1 7 5 3 4 3             1 3 1 7 5 3 4 3              
       2 1 5 1                     2 1 5 1

For the example above, the problem can be stated as the two lists [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] and [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] which give the "solid" lengths of the rows and columns, top-to-bottom and left-to-right, respectively. Published puzzles are larger than this example, e.g. 25 x 20, and apparently always have unique solutions.

解题

将二维表格以线性的列表表示，MxN的表格表示为长度为的列表。用回溯法探索列表中所有元素的标记组合，边探边排除不符合约束的组合。剩下的即为可行解。

代码实现

def nonograms(rowBitmaps, columnBitmaps): rowCount = len(rowBitmaps) columnCount = len(columnBitmaps) count = rowCount * columnCount return resolveNonograms(count, [], rowBitmaps, columnBitmaps) def resolveNonograms(n, solution, rowBitmaps, columnBitmaps): if n == 0: return [[]] result = [[mark]+remain for mark in [True, False] for remain in resolveNonograms(n-1, solution + [mark], rowBitmaps, columnBitmaps) if isNotViolate(solution+[mark], rowBitmaps, columnBitmaps)] return result def isNotViolate(partialSolution, rowBitmaps, columnBitmaps): nRow = len(rowBitmaps) nCol = len(columnBitmaps) for rowIndex, bitmaps in enumerate(rowBitmaps): if len(partialSolution) >= (rowIndex+1) * nCol: if bitmaps != countBitmaps(partialSolution[rowIndex*nCol:(rowIndex+1)*nCol]): return False for columnIndex, bitmaps in enumerate(columnBitmaps): cellOfColumn = [] for index, value in enumerate(partialSolution): if index % nRow == columnIndex: cellOfColumn.append(value) if len(partialSolution) >= (nRow-1)*nCol +columnIndex +1: if bitmaps != countBitmaps(cellOfColumn): return False return True def countBitmaps(l): trueCount = 0 bitmaps = [] for v in l: if v is False and trueCount != 0: bitmaps.append(trueCount) trueCount = 0 if v is True: trueCount = trueCount + 1 if trueCount != 0: bitmaps.append(trueCount) return bitmaps

results matching ""

    No results matching ""