1

I'm writing an algorithm to solve 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.

All the basic techniques are implemented and working, but I've realized that with bigger puzzles (5x5>) I need some sort of recursive algorithm. I found a decent working python script, but I'm not really following what it actually does beyond solving basic clues.

Does anyone know the proper way of solving these puzzles or can anyone reveal the essentials in the code above?

4

2 回答 2

9

米莎向你展示了蛮力的方式。可以基于约束传播制定一个更快的递归算法。Peter Norvig（Google Research 负责人）写了一篇关于如何使用这种技术用 python 解决数独的优秀文章。阅读并尝试理解每一个细节，保证你会学到很多东西。由于摩天大楼谜题与数独有很多共同点（没有 3X3 块，但边缘上的数字给出了一些额外的限制），你可能会窃取他的很多代码。

你开始，就像数独一样，每个字段都有一个从 1..N 开始的所有可能数字的列表。之后，您一次查​​看一条水平/垂直线或边缘线索并删除非法选项。例如，在 5x5 的情况下，3 的边将前两个中的 5 和第一个正方形中的 4 排除在外。约束传播应该完成其余的工作。继续循环遍历边缘约束，直到它们被满足，或者在循环遍历所有约束后卡住。如 Norvig 所示，然后您开始猜测并删除数字以防出现矛盾。

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

于 2013-09-18T13:55:00.890 回答
5

如果你很绝望，你可以暴力破解谜题。我通常这样做是熟悉谜题的第一步。基本上，您需要NxN使用从 1 到 N （含）的整数填充正方形，遵循以下约束：

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

蛮力解决方案将像这样工作。首先，将棋盘表示为一个二维整数数组。然后编写一个函数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)or(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选择下一个要填充的正方形。最简单的方法就是对板进行扫描线遍历。更聪明的方法是交替填充行和列。

于 2013-09-18T13:30:08.053 回答