啓發式的移陣列

Question

給定一個目標狀態

int final[3][3]={{1,2,3}, 
       {4,5,6}, 
       {7,8,9}}; 

和隨機初始狀態，我想只有通過把行（右或左）和列（上下），以我的數組作爲最終排序我表

7 8 4 by shifting to the right the first row it will become 4 7 8 
    2 1 9               2 1 9 
    6 5 3               6 5 3 

所以我想用*搜索，我試圖找到一個很好的啓發式。

我已經嘗試過誤放數組元素。

有什麼建議嗎？

Answer 1

我認爲這是一個代數問題。你會得到一組由6個週期（3行3列）產生的排列，你希望找到更多的步驟來幫助你實現任何排列。

第一個建議：並非所有的排列都是可能的！由於每個轉換都是偶數排列（3個週期是兩個轉置的組合），所以只有偶數排列纔是可能的。因此，如果（2,1,3），（4,5,6），（7,8,9）中沒有找到任何解決方案，那麼所有的配置都有兩個交換數字。

第二個建議。如果r是一個行位移並且c是一個coumn位移，那麼計算rcr'c'的作用，其中r'和c'是反向位移。這個「換向器」又是一個由3個元素組成的循環，但是這次它們不在一行或一列中。通過選擇不同的r和c，你可以得到很多3個循環，可以在第三個建議中使用。

第三意見。考慮已經處於最終位置的數字區域。應用3個週期來補充這個集合以減少它，直到你找到解決方案。