魔方加扰算法 - JavaScript

Question

最近在做一个魔方计时网站，需要做一个打乱算法。我将介绍加扰算法的工作原理：每张脸都有自己的字母，这是首字母。例如，如果你想移动正面，你会写“F”。如果你想移动右边的脸，你会写“R”，等等。只是注意底面是D，至于向下。所以你有 D U R L B F。如果该字母后没有任何内容，则顺时针旋转。如果有撇号“‘”，则将其逆时针旋转。如果有 2，则将其转动两次。现在的问题是你不能让两个相同的字母彼此相邻，因为它们会取消（例如“.. U U' ...”等同于什么都不做。到目前为止，我已经解决了这个问题我的算法。当您有一个字母，然后是相反的字母，然后是第一个字母时，问题就来了（例如“.. U D U'...”（表示顺时针向上，顺时针向下，逆时针向上））。我不知道如何检查这些并自动避免它们。这是代码：

<div id=“Scramble”></div>
<script>
generateScramble();

function generateScramble() {

  // Possible Letters
  var array = new Array(" U", " D", " R", " L", " F", " B")

  // Possible switches
  var switches = ["", "\'", "2"]; 

  var array2 = new Array(); // The Scramble.

  var last = ''; // Last used letter

  var random = 0;

  for (var i = 0; i < 20; i++) {
      // the following loop runs until the last one 
      // letter is another of the new one
      do {
         random = Math.floor(Math.random() * array.length);
      } while (last == array[random]) 

  // assigns the new one as the last one
  last = array[random];

  // the scramble item is the letter
  // with (or without) a switch
  var scrambleItem = array[random] + switches[parseInt(Math.random()*switches.length)];

  array2.push(scrambleItem); // Get letters in random order in the array.
  }

  var scramble = "Scramble: ";

  // Appends all scramble items to scramble variable
  for(i=0; i<20; i++) {
     scramble += array2[i];
  }

  document.getElementById("Scramble").innerHTML = scramble; // Display the scramble
}
</script>

Answer 1

对于 Rubik;s 魔方的初学者 God's Number is 20 所以你只有 20 步而不是 25 步。我假设你没有进行加扰（如你的标题所示），而是为 genere&test 求解器类型生成求解命令字符串.有太多序列相互抵消，检查所有序列很可能比实际尝试慢。

问题是即使 O(n^20) 也很大，您需要降低 20。这是通过 LUT 保持半解决状态来完成的。例如，为 5 轮加扰的所有组合创建 table 保持状态。然后将其用作结束条件，将求解器变为 O(n^15 + n^5) = O(n^15) ...

魔方加扰算法 - JavaScript

Rubik´Cube Scrambling Algorithm - JavaScript

javascript

algorithm

rubiks-cube