javascript - 魔方加扰算法 - JavaScript

标签 javascript algorithm rubiks-cube

我一直在做一个魔方计时器网站,我需要做一个加扰算法。我将介绍加扰算法的工作原理: 每张脸都有自己的字母,这是首字母。例如,如果你想移动正面,你会写“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>

最佳答案

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

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

关于javascript - 魔方加扰算法 - JavaScript,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47247087/

相关文章:

javascript - 魔方的随机移动 javascript 扰码器

javascript - 仅使用 javascript 和 'this' 更改 img 源 onmouseover

android - Marker Recognition on Android(识别魔方)

python - 在 Python 中使用字典代替 Case/Switch 语句

r - 如何生成和绘制所有生成树?

algorithm - 迭代格雷码更改位置的有效方法

java - 这个算法是免费的吗?

php - 摆脱这个代理

javascript - 正则表达式仅检查数字(负数和正数)

javascript - Rails 4 - 不包含 js 或图像的 heroku 生产版本