如何以編程方式解決15（移動數字）難題？

你們所有人都可能看到了移動的數字/圖片拼圖。一，你有數字1到15 4x4的方格，並試圖從隨機起始位置，讓他們如何以編程方式解決15（移動數字）難題？

我的女朋友還是我的一些非程序員的朋友可以與一些mumbo-解決這個巨無霸，他們無法向我解釋。我無法解決這個難題。

最有前途的方法我發現是解決第一排，然後我會得到

1 2 3 4 
X X X X 
X X X X 
X X X

然後第一列不接觸解決細胞

1 2 3 4 
5 X X X 
9 X X X 
13 X X

然後第二行

then second column

問題是，剩下的X（隨機）瓷磚有時是無法解決的位置，這是我的解決方案失敗的地方。但我覺得我正走在正確的道路上。

如果可能的話，我的程序通過嘗試將數字X指定到指定的位置而不會弄亂正確的單元格來解決指定的行/列。但它不能做2x2網格上的最後3個瓦片。我錯過了什麼？

來源

2010-09-01 Axarydax

感謝所有的回覆！ – Axarydax 2010-09-01 20:12:07

感謝您發佈此方法。我爲iOS開發了一款Slide Puzzle應用，並解決了4x4 Slide Puzzle的難題。我已經使用這種方法並在314步驟中解決了這個問題。 – 2013-02-24 10:46:40

你絕對是在正確的軌道上，而不是迭代地解決行/列解決問題的方法，直到你有一個最小化的3x3，然後解決這個問題。 3x3是您正確重新排列網格所需的最小尺寸（而2x2不會像您已經討論的那樣爲您提供完全的靈活性）。這種方法是可擴展的太 - 你能解決5x5的，10×10等

來源

2010-09-01 19:59:08 Rudu

我一直認爲3×2是最小的靈活尺寸，而不是3×3。 – 2010-10-09 18:26:47

所以最小的靈活尺寸是3×2或3×3？ – Axarydax 2012-03-20 18:54:41

這site有關於3x3網格很好的解釋，你可能很容易擴展到4x4。

來源

2010-09-01 19:55:16 GWW

確保您的拼圖首先解決。 Not all are。

否則你的策略看起來很合理。

來源

2010-09-01 19:56:50 John

非常有趣，但我肯定他的原始算法仍然可以通過可解決的數字訂單失敗。 – userx 2010-09-05 23:10:32

userx：你有參考嗎？我很樂意看到它。他認爲算法的哪一部分可能會失敗？我看到的唯一可能失敗的部分就是解決最後的2x3塊，但看起來好像不會。唯一的技巧就是讓左邊的兩塊放在右邊的空間裏（比如上面的標準4x4上的10和14）。那時候，其餘三個都是正確排列的，否則就不是。然後，它回到原來的難題是否可以解決。 – John 2010-09-07 15:08:49

如何確定拼圖是否可解？ – 2016-02-25 16:11:34

通過減少你解決不了的唯一可能的情況下，形式必須是
1 3
2 X
並且要得到它
1 2
3 X

使用一個額外的行和列，你可以用一個簡單的預先計算的序列搬完到適當的位置

來源

2010-09-01 19:59:54

任何給定的人總是有最多4個移動位置。我想知道遍歷所有選項建立2-4樹的簡單算法是否會達到「解決」的位置或堆棧溢出:)

來源

2010-09-02 19:50:11 Grozz

我不需要任何複雜的東西，我已經有一個簡單的算法，試圖解決它像「找到號碼1並將其移動到左上角」，「找到第二個，並將其移動到它的位置，地點3和4並一起移動到第一排，但問題在於最後一個2x3或3x3塊。 – Axarydax 2010-09-03 09:56:35

我認爲解決這個問題的最有效方法是使用添加模式，可以啓發的，IDA *算法。如此處所述 - http://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf。（我認爲費爾納告訴我們，他找到了一種更好的方式，但我不記得它是什麼（雙向A *？），但無論如何這應該是足夠的（ - ：）。
無論如何，這個課程很長之前，所以我建議閱讀文章..
HTH。保重

來源

2010-09-05 22:57:44

原始海報描述的解決方案策略將始終適用於標準的可解15拼圖如果Axarydax可以減少15拼圖到如果我們將拼圖中的空白處理爲一個拼圖，那麼每個合法移動都涉及到交換該相鄰ti的空白「瓦片」樂。這使我們可以將拼圖上的運動視爲16個字符的排列。也就是說，對稱組S 的元素。每個原始動作只是兩個元素之間的「交換」或轉置（其中之一是空白）。

由於拼圖在右下角的空白拼貼開始和結束，空白拼貼必須移動偶數次才能解開拼圖。（這是通過想象在拼圖頂部重疊的棋盤圖案最容易看到的 - 在奇數次移動之後，空白將會在不同的顏色方塊上）。這意味着所制定的解決方案必須是均勻排列的產物，所以它必須是交替組A 的元素，其具有正好一半的S 。（在16個排列中，有16個排列是偶數，而16個排列是偶數，而且甚至是偶數偶數偶數偶數偶數奇數偶數偶數）

如果必要的校正排列碰巧是奇怪的，無論您做什麼，都無法解決這個難題。如果所需的校正置換是均勻的，並且如果Axarydax遵循所描述的策略，則對於剩餘的2×2塊所需的置換將必然是固定空白正方形的偶數置換。僅三個元素的唯一偶數排列是旋轉1-> 2-> 3-> 1（循環記號（123））和1-> 3-> 2-> 1（循環記號（132））。這些很容易在其餘四個方格上進行，而不會打擾其他方格。因爲Axarydax無法弄清楚2x2塊的這些微不足道的解決方案是不合情理的，所以我懷疑他/她已被惡作劇，或者試圖使用的15個難題在某種程度上是非標準的。

來源

2010-10-15 20:12:06 Josephine

如何以編程方式解決15（移動數字）難題？

回答

相關問題