摩天大楼拼图算法

Question

我正在编写一个算法来解决摩天大楼谜题

摩天大楼拼图将数独的行列约束与外部线索值结合起来，将每一行或每一列数字重新想象成一条充满不同高度摩天大楼的道路。更高的数字代表着更高的建筑。 要解决天敌之谜，你必须把1到5，或1到任何大小的谜题，一次每一行和每列，同时也解决每一个给定的摩天大楼线索。 要理解天书谜题，你必须想象一下，你在网格中放置的每一个值都代表着那几层楼中的摩天大楼。1是1层的摩天大楼，4是4层的摩天大楼.现在想象一下，你站在网格之外，其中一个线索数字是，然后回首网格。这个线索数告诉你从这一点可以看到多少摩天大楼，只能沿着线索所在的那一排或一列看，从线索的角度看。较高的建筑物总是掩盖较低的建筑物，所以换句话说，较高的数字总是隐藏较低的数字。

所有的基本技术都是实现和工作的，但我已经意识到，对于更大的谜题(5x5>)，我需要某种递归算法。我找到了一个不错的工作python脚本，但除了解决基本线索之外，我并没有真正遵循它的实际操作。

有没有人知道解决这些谜题的正确方法，或者谁能透露上面代码中的要点？

Answer 1

米莎给你展示了蛮力的方法。在约束传播的基础上，可以实现更快的递归算法。Peter ( Google的负责人)写了一个关于如何使用这种技术解决python的Sudoku问题的优秀文章。读一读，试着理解每一个细节，你会学到很多，保证。由于摩天大楼拼图与Sudoku有很多共同之处(没有3X3块，但边缘的数字给出了一些额外的限制)，您可能会盗取他的大量代码。

首先，就像Sudoku一样，每个字段都有一个列表，列出1.N中所有可能的数字，然后，每次查看一条水平/垂直线或边缘线索，并删除非法选项。例如，在5x5的情况下，3的边从前2中排除5，从第一正方形中排除4。约束传播应该完成其余的工作。一直循环通过边缘约束，直到它们得到满足，否则你会在循环通过所有约束后陷入困境。正如Norvig所示，在出现矛盾的情况下，您可以开始猜测和删除数字。

在数独的情况下，一个给定的线索只需要处理一次，因为一旦你给一个正方形分配了一个数字(你去掉了所有其他可能性)，所有线索的信息都被使用了。然而，对于摩天大楼，你可能需要多次使用给定的线索，直到它完全满足为止(例如，当整条线被解决时)。

Answer 2

如果你绝望了，你可以用暴力来解决这个难题。我通常这样做，作为第一步，以熟悉这个谜题。基本上，您需要使用从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选择要填充的下一个正方形。最简单的方法，这只是一个扫描线遍历板。一种更明智的方法是交替填充行和列。