斯卡拉 - 摩天大樓拼圖

我有一個任務，我應該在任何給定的NxN中解決摩天大樓的難題（http://www.brainbashers.com/skyscrapershelp.asp）。我試圖制定一個蠻力的解決方案，但是由於我運行了它，它似乎不會很快完成（現在運行了一個小時，沒有最後一個單元更新過去「1」）。我一直在研究算法以更有效的方式解決這個難題，但我並不真正瞭解它是如何工作的。我已經設置了一個程序，可以設置：斯卡拉 - 摩天大樓拼圖

1）測試提示的大小與拼圖的大小（例如，5x5拼圖中的5），這意味着相鄰的行必須從1開始旁邊的提示，增加1到拼圖的大小（在前面的例子中，5，即1,2,3,4,5）。

2）對值爲1的提示進行測試，這意味着相鄰字段必須是智力遊戲的最大尺寸（在前面的示例中爲5）。但在此之後，我並不真正知道下一步我的代碼。我知道如何解決一個特定大小的難題（例如4x4），但問題是爲NxN難題開發一個難題...我發現這個：Skyscraper puzzle algorithm 但我並不真正瞭解那裏提供的答案。我也發現這個：http://www.wikihow.com/Solve-a-Skyscrapers-Puzzle 但它是一個具體的例子，我真的不知道如何將它轉換成NxN算法。

我不能發佈兩個以上的鏈接，所以我會發布鏈接到我的代碼（包括蠻力解決方案，以及我在算法中的一個），作爲對這個問題的評論。感謝您的時間！

來源

2013-10-13 user2875994

這裏是我的蠻力解決方案（不是100％確定它是否有效，但是，因爲我永遠不會真正測試它是否工作，因爲它需要運行多長時間）：http://pastebin.com/jzbzGAwN 這就像我已經提出的算法解決方案：http://pastebin.com/HFc9HxKz ，你可以看到我有一個「updateTrueValues」函數處理董事會，並試圖削減可能的值爲田野。 – user2875994

這裏有一個方法，將工作：

1）爲網格尺寸，生成數字的所有排列的數組。例如，在一個4x4的，你得[1234，1243，1324，1342，1423，1432，2134，2143，2314，2341，等]

2）然後爲每個的，計算從可見的摩天大樓左邊和右邊。 [1234，4，1]，[1243，3，2]，[1324，3，1]，...

3）爲了您的拼圖的每一行，生成摩天大樓的名單，將工作通過從步驟2中選擇與拼圖左側和右側的數字相匹配的行。

4）所以，現在你可能有1爲第1,3行工作，第2行工作，第2行工作，第2行工作，第4行工作。第4行是暴力部分。你想嘗試所有這些組合，並測試，看看他們是否滿足頂部和底部的數字。對於我的例子，你必須測試1 * 3 * 2 * 2 = 12的組合來找到一個有效的。您還需要驗證每列包含每個數字。

來源

2013-10-13 12:42:30 vacawama

感謝您的回覆。我理解你的概念/邏輯以及它的工作方式，但我不知道如何實現它。特別是在斯卡拉。從1）開始，我想我已經想出瞭如何打印出從0到N的整數數組的所有排列（如下所示：http://stackoverflow.com/questions/13218019/generating-permutations-of -an-int-array-using-java-erro），但創建一個包含所有排列的新數組超出了我目前能做的。 – user2875994

斯卡拉 - 摩天大樓拼圖

回答

相關問題