Алгоритм скремблирования Rubik´Cube - JavaScript

Question

Я работал над сайтом Rubik's Cube Timer, и мне нужно создать алгоритм шифрования. Я расскажу, как должен работать алгоритм скремблирования: у каждого лица свое письмо, оно начальное. Например, если вы хотите переместить переднюю грань, вы должны написать "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

Начнем с того, что число Бога для кубика Рубика равно 20, поэтому вы получили только 20 ходов вместо 25. Я предполагаю, что вы не делаете скремблирование (как подсказывает ваш заголовок), а вместо этого генерируете строки команд решения для жанра и тестирующего типа решателя. Слишком много последовательностей, которые отменяют друг друга, и проверять их все, скорее всего, будет медленнее, чем проверять их на самом деле.

Проблема в том, что даже O(n^20) огромен, и вам нужно снизить 20, Это сделано ЛУТ, держащим полуразрешенные государства. Например, создать состояние удержания таблицы для всех комбинаций скремблирования на 5 ходов. Затем используйте это как конечное условие, превращая ваш решатель в O(n^15 + n^5) = O(n^15)...