摩天大楼拼图算法

Question

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

摩天大楼的谜题将数独的行和列限制与外部线索值相结合,外部线索值将每行或每列数字重新设想为充满不同高度的摩天大楼的道路.数字越大表示建筑物越高.

要解决摩天大楼之谜,您必须将1到5或1放置到任何大小的拼图中,每次放入每一行和每列,同时还要解决每个给定的摩天大楼线索.

要了解摩天大楼的谜题,您必须想象您放入网格中的每个值都代表了这个楼层的摩天大楼.因此,1楼是1层楼的摩天大楼,4楼是4层楼的摩天大楼.现在想象一下,你站在网格之外,其中一条线索数字是回到网格中.该线索数字告诉您从该点可以看到多少个摩天大楼,仅沿着线索所在的行或列,以及从线索的角度来看.较高的建筑物总是掩盖较低的建筑物,因此换句话说,较高的数字总是隐藏较低的数字.

所有的基本技术都已实现并正常工作,但我已经意识到,对于更大的难题(5x5>),我需要某种递归算法.我找到了一个体面的工作python脚本,但我并没有真正关注它除了解决基本线索之外的实际操作.

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

Answer 1

Misha向你展示了蛮力的方式.可以基于约束传播来制作更快的递归算法.Peter Norvig(Google Research的负责人)撰写了一篇关于如何使用这种技术解决数字与Python 的优秀文章.阅读它并尝试了解每一个细节,你会学到很多东西,保证.由于摩天大楼拼图与Sudoku有很多共同点(没有3X3块,但边缘的数字给出了一些额外的限制),你可能会盗取他的很多代码.

你可以像Sudoku一样开始,每个字段都有一个1..N所有可能数字的列表.之后,您一次查​​看一条水平/垂直线或边缘线索,并删除非法选项.例如,在5x5的情况下,3的边缘从前两个中排除5,从第一个方格中排除4.约束传播应该完成其余的工作.保持循环超过边缘约束,直到它们满足为止,或者在循环通过所有约束后卡住.如Norvig所示,您可以在出现矛盾时开始猜测并删除数字.

在数独的情况下,给定的线索只需要处理一次,因为一旦你将一个数字分配给一个方格(你删除所有其他可能性),线索的所有信息都已被使用.然而,对于摩天大楼,您可能需要多次应用给定线索,直到完全满意为止(例如,当完整线路被解决时).

Answer 2

如果你绝望了，你可以暴力破解这个谜题。我通常这样做是熟悉这个谜题的第一步。基本上，您需要用NxN1 到 N 之间的整数填充正方形，并遵循以下约束：

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

暴力解决方案将像这样工作。首先，将棋盘表示为二维整数数组。然后编写一个函数is_valid_solution，如果棋盘满足上述约束，则返回 True，否则返回 False。这部分在.net中是比较容易做的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选择下一个要填充的方块。最简单的方法就是对棋盘进行扫描线遍历。更聪明的方法是交替填充行和列。