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伪随机洗牌？

回答

相关问题