摩天大楼拼图算法 [英] Skyscraper puzzle algorithm

问题描述

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

I'm writing an algorithm to solve skyscrapers puzzles:

摩天大楼拼图数独相结合的行和列的约束与重新想象号的每一行或列作为一个完整的不同高度的摩天大楼路外部线索值。数值越大，再present更高层的楼宇。

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.

要解决一个谜题的摩天大楼，你必须将1至5或1到任何拼图的大小，每一次到每行和列，同时还解决每个给定的摩天大楼线索。

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.

要理解摩天大楼的困惑，你必须想象你放入网格重$ P $每个值psents的楼层数的摩天大楼。所以1是1楼的摩天大楼，而4是一个4层楼的摩天楼。现在想象一下你去站在电网所在的线索号码之一就是外面看回电网。这一线索数字告诉你，你可以有多少摩天大楼从这一点看，只有看沿行或​​列中的线索，并从来看线索的地步。更高的建筑总是默默无闻较低的建筑物，所以换句话说，更高的数字总是难掩较低的数字。

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.

所有的基本技术实现和工作，但我已经意识到，有更大的困惑（5×5>）我需要某种形式的递归算法的。我找到了一个体面的工作 python脚本的，但我没有真正下它实际上没有超出解决基本线索。

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.

有谁知道解决这些难题的正确方法或任何人都可以显示在code中的必需品上面？

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

推荐答案

米沙显示你的蛮力方式。一种快得多的递归算法可以根据约束传播进行。彼得·诺维格（头谷歌研究）写href="http://norvig.com/sudoku.html" rel="nofollow">有关如何使用这种技术来解决数独与Python优秀的文章的

Misha showed you the brute-force way. A much faster recursive algorithm can be made based on constraint propagation. Peter Norvig (head of Google Research) wrote an excellent article about how to use this technique to solve Sudoku with python. Read it and try to understand every detail, you will learn a lot, guaranteed. Since the skyscraper puzzle has a lot in common with Sudoku (without the 3X3 blocks, but with some extra constraints given by the numbers on the edge), you could probably steal a lot of his code.

您启动，与独，其中每个字段具有从1..N所有可能的数字的列表。在这之后，你看一次在一个水平/垂直线或边缘线索，拆除违法选项。例如。在5×5的情况下，为3的边缘排除5从前两个和4从第一正方形。约束传播应该做休息​​。保持遍历边缘约束，直到他们得到满足或者您遇到过的所有约束循环之后。因此，如弱势族群，你再开始猜测，并在发生矛盾删除号码。

You start, as with Sudoku, where each field has a list of all the possible numbers from 1..N. After that, you look at one horizontal/vertical line or edge clue at a time and remove illegal options. E.g. in a 5x5 case, an edge of 3 excludes 5 from the first two and 4 from the first squares. The constraint propagation should do the rest. Keep looping over edge constraints until they are fulfilled or you get stuck after cycling through all constraints. As shown by Norvig, you then start guessing and remove numbers in case of a contradiction.

在案件的数独，一个给定的线索只有一次被处理，因为一旦你分配一个号码，以一平方（删除所有其他的可能性），已使用线索的所有信息。随着摩天大楼，但是，你可能需要用一个给定的线索，好几次，直至完全满足（例如，当整条生产线解决）。

In case of Sudoku, a given clue has to be processed only once, since once you assign a single number to one square (you remove all the other possibilities), all the information of the clue has been used. With the skyscrapers, however, you might have to apply a given clue several times until it is totally satisfied (e.g. when the complete line is solved).

这篇关于摩天大楼拼图算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！