摩天大楼拼图算法

Question

我正在编写一个算法来解决skyscrapers puzzles：

Skyscraper puzzles combine the row and column constraints of Sudoku with external clue values that re-imagine each row or column of numbers as a road full of skyscrapers of varying height. Higher numbers represent higher buildings.

To solve a Skyscraper puzzle you must place 1 to 5, or 1 to whatever the size of the puzzle is, once each into every row and column, while also solving each of the given skyscraper clues.

To understand Skyscraper puzzles, you must imagine that each value you place into the grid represents a skyscraper of that number of floors. So a 1 is a 1-floor skyscraper, while a 4 is a 4-floor skyscraper. Now imagine that you go and stand outside the grid where one of the clue numbers is and look back into the grid. That clue number tells you how many skyscrapers you can see from that point, looking only along the row or column where the clue is, and from the point of view of the clue. Taller buildings always obscure lower buildings, so in other words higher numbers always conceal lower numbers.

所有的基本技术都已经实现并运行，但我已经意识到，对于更大的难题（5x5>；），我需要某种递归算法。我找到了一份体面的工作，但除了解决基本的线索之外，我并没有真正遵循它的实际功能。

有人知道解决这些难题的正确方法吗？或者有人能揭示上面代码中的要点吗？

Answer 1

如果你绝望了，你可以用暴力破解这个谜题。我通常把这作为熟悉拼图的第一步。基本上，您需要使用从1到N（包括1到N）的整数填充NxN平方，遵循以下约束：

• 每一行中的每个整数只出现一次
• 每列中的每个整数只出现一次
• 排“线索”满意
• “线索”栏满意

暴力解决方案会这样工作。首先，将电路板表示为二维整数数组。然后编写一个函数is_valid_solution，如果电路板满足上述约束，则返回True，否则返回False。这一部分在O(N^2)中相对容易完成。

最后，遍历可能的板置换，并为每个置换调用is_valid_solution。当它返回True时，您就找到了一个解决方案。总共有N^(NxN)种可能的安排，因此您的完整解决方案是O(N^(NxN))。通过使用上述约束来减少搜索空间，您可以做得更好。

上面的方法需要相当长的时间来运行（O(N^(NxN))对于一个算法来说是非常糟糕的），但是您（最终）会得到一个解决方案。当你有工作的时候，试着想一个更好的方法去做；如果你被卡住了，那就回来。

编辑

与上述方法相比，另一个更好的选择是从一块空木板开始进行搜索（例如深度优先）。在搜索的每次迭代中，您都要用一个数字填充表的一个单元格（同时不违反任何约束）。一旦你刚好填满了棋盘，你就完了。

这是递归强力深度优先搜索的伪代码。搜索深度为NxN个节点，每个节点的分支因子最多为N。这意味着您最多需要检查1 + N + N^2 + ... + N^(N-1)或(N^N-1)/(N-1)个节点。对于这些节点中的每一个，您都需要调用is_valid_board，在最坏的情况下（当电路板已满时），它是O（N^2）。

def fill_square(board, row, column):
  if row == column == N-1: # the board is full, we're done
    print board
    return
  next_row, next_col = calculate_next_position(row, col)
  for value in range(1, N+1):
    next_board = copy.deepcopy(board)
    next_board[row][col] = value
    if is_valid_board(next_board):
      fill_square(next_board, next_row, next_col)

board = initialize_board()
fill_square(board, 0, 0)

函数calculate_next_position选择要填充的下一个正方形。最简单的方法就是扫描线路板。更聪明的方法是交替填充行和列。

Answer 2

米莎向你展示了暴力的方式。基于constraint propagation可以生成更快的递归算法。Peter Norvig（Google Research的负责人）写了一篇excellent article关于如何使用这种技术用python解决数独问题的文章。读一读，试着理解每一个细节，你会学到很多，保证。由于摩天大楼拼图和数独游戏有很多共同点（没有3X3块，但是边上的数字给了一些额外的限制），你可能会窃取他的很多代码。

从数独开始，每个字段都有一个从1到N的所有可能数字的列表。然后，每次查看一条水平/垂直线或边缘线索，并删除非法选项。E、 g.在5x5的情况下，3的边从前两个方格中排除5，从第一个方格中排除4。剩下的工作应该由约束传播来完成。继续循环边约束，直到它们得到满足，或者在循环通过所有约束后卡住。如Norvig所示，然后开始猜测并删除数字，以防出现矛盾。

在数独游戏中，一条给定的线索只需要处理一次，因为一旦你给一个正方形分配了一个数字（你去掉了所有其他可能性），线索的所有信息都被使用了。然而，对于摩天大楼，您可能需要多次应用给定的线索，直到完全满意为止（例如，当整条线解出时）。