0

I have been working on a Rubik’s Cube Timer website, and I need to make a scrambling algorithm. I’ll go over how the scrambling algorithm should work: Each face has it’s own letter, it’s initial. for examble, if you want to move the front face, you would write “ F “. If you want to move the the right face, you would write “ R “, and so on. just note that the bottom face is D, as for down. So you have D U R L B F. If there is nothing after that letter, you turn it clockwise. If there is an appostrophe “ ‘ “, you turn it counter-clockwise. If there is a 2, you turn it two times. Now the thing is that you cannot have 2 same letters next to oneanother, as they would cancel (For example “.. U U’ ...” would be the same as doing nothing. So far, I have this taken care of in my algorithm. The problem comes when you have one letter, then it’s opposite, then again the first letter, ( For example “.. U D U’...” (would mean Up clockwise, Down clockwise, Up counterclokwise)). I have no idea how to check for these and avoid them automatically. Here’s the code:

<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>
Jakub Chaloupka
  • 177
  • 1
  • 3
  • 12
  • A naive way: 1) find sequence between action U and and reverse U' 2) the sequence is only valid if the face U is changed during this sequence (easy to proof, since you know which actions change U) if U is not changed during the sequence remove U,U' from the scramble list and start again on the beginning of the list. Otherwise look at next element of the list -- If you do this until you reach the end of the scramble list, only valid sequences will remain... (but i am sure there is a more efiicent way) – goeddek Nov 12 '17 at 09:42
  • Thank you, I will try it out – Jakub Chaloupka Nov 12 '17 at 10:22
  • Actually maybe not, I am sorry, I explained it badly. You cannot have for example U D U’, but neither U D U or U D U2, because there is a limited number of moves, (25 for the classical rubik’s cube), and U D U would be the same as doing U2 D, or U D U2 would be the same as doing U’ D. And that would waste moves and that would result in poorly scrambled cube, moreover if it happens more times during one solve. So I apologize for explaining it badly in the beginning – Jakub Chaloupka Nov 12 '17 at 10:30
  • the lagorithm should still work, you just have to model more cases. so for U D .. U' its {} and for U D .. U its U2 D .. There are not that many cases... – goeddek Nov 12 '17 at 12:12

1 Answers1

1

For starters God's Number is 20 for Rubik;s cube so you got only 20 moves instead of 25. I assume you are not doing scrambling (as your title suggest) but instead generate solution command strings for genere&test solver type. There are too many sequences that cancel each other and to check for all of them would be most likely slower than try them out actually.

The problem is that even O(n^20) is huge and you need to lower the 20. That is done by LUT holding semi solved states. For example create table holding states for all combinations of 5 turn scrambling. Then use that as end condition turning your solver into O(n^15 + n^5) = O(n^15) ...

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • I used to have it 20 moves long, but I chcekef the Legacy WCA Scrambler and It had 25 moves so that’s why I’ve changed it. But it’s the old JavaScript version so that may be why – Jakub Chaloupka Nov 13 '17 at 07:43
  • @JakubChaloupka btw if you need just a solver (not the best solution) you can use the human algos for that see [Quaternion rotation do not works as excepted](https://stackoverflow.com/a/39024016/2521214). Also as the comments suggest scanning ahead for reverse turn is quite simple but the speed up is questionable and highly depends on the implementation. – Spektre Nov 13 '17 at 15:29
  • @JakubChaloupka then you do not need to worry about duplicity or self anihilating moves ... do 50 random moves and that is it ... – Spektre Nov 13 '17 at 20:00