N-Puzzle僞隨機洗牌？

我正在研究N-Puzzle遊戲（也稱爲15-謎題...），您可以在一個方形網格上拆分圖像，移除一個部分並隨機播放。我對這個難題的解決方案不太感興趣，因爲這取決於用戶。但我想僞隨機洗牌。N-Puzzle僞隨機洗牌？

我知道1/2所有可能的洗牌都會讓董事會無法解決。假設我有一些rand（） - esc函數，並且我知道棋盤大小，是否有一種簡單的方法可以隨意地生成混洗狀態？

我在內存中有一個遊戲板，一個整數的多維數組。我的方法只是將圖像按照相反的順序放置，在偶數板上將第二張圖像切換爲最後一張圖像。我目前的功能在下面，我正在使用Java。

private void shuffle() 
{ 
    gameState = new int[difficulty][difficulty]; 
    int i = 0, N = (difficulty * difficulty) -1; 

    while (i < N) 
     gameState[(int)(i/difficulty)][i % difficulty] = N - ++i; 
    gameState[difficulty-1][difficulty-1] = N; 

    // N id even when the remainder of N/2 is 0 
    if ((difficulty % 2) == 0) 
    { 
     // swap 2nd to last and 3rd to last element 
     int tmpEl = gameState[difficulty-1][difficulty-2]; 
     if (difficulty == 2) 
     { 
      gameState[1][0] = gameState[0][1]; 
      gameState[0][1] = tmpEl; 
     } 
     else 
     { 
      gameState[difficulty-1][difficulty-2] = gameState[difficulty-1][difficulty-3]; 
      gameState[difficulty-1][difficulty-3] = tmpEl; 
     } 
    } 
}

來源

2011-05-23 Tom

可能的重複[如何確保當我洗牌我的謎題時，我仍然以偶數排列？]（http://stackoverflow.com/questions/2653694/how-can-i-ensure-that-當我洗牌我的謎題我仍然結束與一個偶數permut） – 2011-05-24 02:01:19

我的建議是跟蹤數組中的空方塊（你已經移除的那塊）。
然後，選擇這個空方塊的任意一邊（確保進行必要的邊界檢查），然後用空方塊「交換」那邊的那塊。這模擬了玩家會做的滑動動作。
多次重複此操作（簡單難度設置 - 難度設置您進行的迭代次數），每次在整個陣列中「滑動」空方塊。

用這種方法，你只需要跟蹤空方塊的位置，然後選擇一個隨機的一面移動到。

希望這可以幫助你一點 - 我沒有提供任何代碼在這裏，只是一個簡單的算法，你可以使用。

來源

2011-05-24 00:08:13

-1。這不會給你一個隨機洗牌，儘管這是問題所要求的。 – 2011-05-24 02:14:40

@Himadri爲什麼不呢？你選擇一個隨機的一面，基本上做的是與用戶做什麼相反，所以據我所知它應該起作用。 – 2011-05-24 21:28:26

假設你只是做了1個動作，那麼明確的結果是不是隨機的權利？只有1次移動，最多隻有4個可能的新位置。 – 2011-05-25 04:55:45

只需生成隨機拼圖，直到生成一個具有偶校驗的拼圖爲止。 http://heuristicswiki.wikispaces.com/N+-+Puzzle

來源

2011-05-24 00:08:17

這個問題基本上歸結爲做一個小扭曲的標準洗牌算法。

關鍵的觀察結果是，對於15個難題是可解的，置換的奇偶性和空白方塊的奇偶性必須相同。

首先爲此使用標準算法創建一個隨機排列。例如Knuth shuffle算法：Random Permutations

使用Knuth的shuffle（或Fisher-Yates shuffle）的優點是它涉及交換數字，因此您可以輕鬆地跟蹤排列的奇偶性。每個交換或者保持奇偶（如果交換1 & 3），或者更改奇偶（如果交換1 & 2）。

將空白方塊放在與置換奇偶性相同的奇偶校驗上，就完成了。如果置換具有奇數奇偶性，則將空白置爲奇數正方形（1,3,5，...隨機選擇）。如果排列有偶數，那麼將空白放在一個平方。

來源

2011-05-24 00:11:18

我很抱歉問這樣一個愚蠢的問題，但這句話是什麼意思？「空白廣場的排列和平價必須是相同的」？排列的平價和空白平方的平價是什麼？ – user151496 2016-04-13 08:38:05

N-Puzzle僞隨機洗牌？

回答

相關問題