7-Riffle Shuffle алгоритм в C# для кубика Рубика - PullRequest
Новая
       51

7-Riffle Shuffle алгоритм в C# для кубика Рубика

0 голосов
/ 08 апреля 2020

Для школьного задания нам нужно реализовать метод 7-Riffle Algorithm в C#, который перетасовывает грани кубика Рубика. К сожалению, в сети недостаточно ресурсов, которые показывают, как это должно быть закодировано. Я уже реализовал секундомер, чтобы вычислить пройденные тики, необходимые для кубиков разных размеров.

Этот код работает на бит перетасовки, но время, которое оно занимает, не имеет смысла, так как оно быстрее, чем у Фишера Йейтса. 

        Random rand = new Random();

        for (int i = rubikCubeArray.Length - 1; i > 7; i--)
        {
            int n = rand.Next(i + 1);
            int temp = rubikCubeArray[i];
            rubikCubeArray[i] = rubikCubeArray[n];
            rubikCubeArray[n] = temp;
        }

Любая помощь, пожалуйста?

1 Ответ

0 голосов
/ 09 апреля 2020

  1. хорошая исходная семя - хорошая идея (как указал jdweng)

    Мне просто нужно исправить эту опечатку, поскольку новички могут не знать, seen должно быть seed. Таким образом, оба сравниваемых алгоритма будут иметь одинаковые условия.

  2. вложенный для циклов

    , не знакомый с 7-Riffle Shuffle Algorithm, но решатель обратного отслеживания должен вложили в петли. Прямо сейчас у вас есть сингл l oop, который проходит 9 раз (почему?).

    Если у вас есть N=7 кубов в случайном порядке, то вам нужно 7 вложенных циклов для каждой итерации по всем возможным оборотам 3*3*2=18. Если N меняется, вам необходимо динамически вкладывать в циклы для получения дополнительной информации см .:

    или маскируемый вложенный для циклов до число богов (20) .

    Каждый для l oop на каждой итерации поворачивает предыдущий куб состояния l oop выбранным движением и в последнем случае l oop также должен обнаруживать раскрытый случай и разрыв, если найден.

    Так что-то вроде этого (решатель): 

    cube0=solved_cube();
for (cube1=cube0,i1=0; i1<18; i1++,cube1=turn_cube(cube0,i1))
 for (cube2=cube1,i2=0; i2<18; i2++,cube2=turn_cube(cube1,i2))
  ...
   for (cube7=cube6,i7=0; i7<18; i7++,cube7=turn_cube(cube1,i7))
    if (cube7 == solved_cube()) return { i1,i2,...,i7 }; // solution found
return false; // unsolved

    , где turn_cube(cube a,int turn) вернет куб a Поворот на turn, где turn выбирает, какой срез поворачивается, в каком направлении (какой из 18 возможных поворотов) ...

Также это может вас заинтересовать:

[Edit1] shuffler

Как я уже говорил, я не знаком с 7 riffle shuffle al go, так что если вы просто хотите получить куб на 7 ходов из решенного состояния, то вы почти правы. У вас должно быть одно for l oop, как у вас есть, но внутри вам нужно сделать правильные случайные перемещения примерно так: 

cube=solved_cube();
for (i=0; i<7; i++)
 cube=turn_cube(cube,Random(18));

Теперь реальная проблема заключается в кодировании функции turn_cube. Чтобы помочь с этим, нам нужно было бы узнать гораздо больше о том, как вы представляете свой кубик Рубика внутри.

Так это массив 1D, 2D или 3D? Какая топология? Каковы значения элементов (HEX цвет может быть или просто 0..5, или с каким-либо перечислением или матрицей преобразования)?

В приведенной выше ссылке приведен пример моего анализатора с исходным кодом для функции void RubiCube::cube_rotate(int axis,int slice,double ang), которая более или меньше, что должен делать cube_turn. Есть 18 возможных поворотов:

  • 3 оси (axis)
  • каждая ось имеет 3 среза (slice)
  • , и мы можем повернуть CW или CCW на 90 градусов (ang, помните, что мои углы указаны в радианах и допускают произвольные углы при анимации поворотов)

, поэтому вам необходимо отобразить эти 18 случаев в int turn = <0,17>, которые будут обработаны в cube_turn и применяется к вашему кубу ...

...