解決一個4x4拼圖網格

我試圖創建一個程序，將發現的步驟來解決以下規則一個難題：解決一個4x4拼圖網格

鑑於任何一組色彩在4x4的方格，試圖匹配具有相同數量的顏色的結束模式。
顏色不交換，但水平或垂直旋轉，使得

{W，W，B，W}

可旋轉以

{W，W，W ，B}

{B，W，W，W}

{W，B，W，W}

整個難題可以用不到16個步驟解決。

我已經想出瞭如何存儲拼圖本身的數據，但我正在努力尋找可以顯示步驟的解決方案。由於深度限制在16步，所以我可以試圖強制這一點，但並不知道如何建立模式。

這類似於解決魔方，我已經看過以下資源：

stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726 ＃34656726
stackoverflow.com/questions/5563671/solving-rubiks-cube-programmatically
amzi.com/articles/rubik.htm
chessandpoker.com/rubiks-cube-solution.html

和15個數字問題

stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15 - 移動 - 數字拼圖

爲了使這個問題儘可能明確：什麼是a）儲存的好方法/打印的步驟，和b）發現，採取至少步驟解決？

來源

2016-01-22 Rhys

*什麼是a）存儲/打印步驟的好方法，b）找到採取最少步驟的解決方案？a）樹。 b）樹分支上的最少節點數。 –

@GilbertLeBlanc，我將如何構造該樹/節點集？只要選擇N個可能的隨機動作（16個方格中的每個方格可能有6個方格就是96個方格）並繼續？ – Rhys

它不是隨機的。根據您自己的示例，您將以4 x 4網格作爲頂級節點。你做所有可能的水平或垂直移動。每一步都是起始位置的一個節點。你走下一個關卡，在每個節點上做同樣的事情，直到你有了解決方案。通過廣度優先搜索，您可以找到最短的解決方案，而無需解決所有問題，但您應該在關係緊密的情況下完成關卡。 –

我想我無法解釋沒有圖片的樹。

說你有這樣的起動方式：

[W, W, W, B] 
[W, W, W, B] 
[B, W, W, W] 
[W, W, W, B]

這將樹的頂級節點。水平0.

所以現在，我們做所有可能的水平和垂直旋轉。水平的第一個右邊。

[B, W, W, W] 
[W, W, W, B] 
[B, W, W, W] 
[W, W, W, B] 

[W, W, W, B] 
[B, W, W, W] 
[B, W, W, W] 
[W, W, W, B] 

[W, W, W, B] 
[W, W, W, B] 
[W, B, W, W] 
[W, W, W, B] 

[W, W, W, B] 
[W, W, W, B] 
[B, W, W, W] 
[B, W, W, W]

水平向左。

[W, W, B, W] 
[W, W, W, B] 
[B, W, W, W] 
[W, W, W, B] 

[W, W, W, B] 
[W, W, B, W] 
[B, W, W, W] 
[W, W, W, B] 

[W, W, W, B] 
[W, W, W, B] 
[W, W, W, B] 
[W, W, W, B] 

[W, W, W, B] 
[W, W, W, B] 
[B, W, W, W] 
[W, W, B, W]

立向上

[W, W, W, B] 
[B, W, W, B] 
[W, W, W, W] 
[W, W, W, B] 

[W, W, W, B] 
[W, W, W, W] 
[B, W, W, B] 
[W, W, W, B]

垂直向下

[W, W, W, B] 
[W, W, W, B] 
[W, W, W, W] 
[B, W, W, B] 

[W, W, W, B] 
[W, W, W, B] 
[B, W, W, B] 
[W, W, W, W]

由於第二和第三列都是W，我們只有2種模式垂直向上和垂直向下。

我們有1級

共有12種模式，我們走得很有條理。我們的舉動沒有隨機性。水平向右，水平向左，垂直向上，垂直向下。

現在，採取級別1的12個模式中的每一個，並生成16個模式。你不必保存匹配在0級和第二級的模式，1

生成和保存的模式彌補了2級

繼續生成每個級別，直到你打16級或你有圖案一個辦法。由於您要刪除樹級別的重複項，因此您不會達到級別16的16至16個電源節點的理論最大值。

如果存在具有最少移動次數的多個解決方案。

來源

2016-01-22 08:54:19

解決一個4x4拼圖網格

回答

相關問題