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>
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) ...