N-Puzzle псевдослучайная перетасовка?

Question

Я работаю над игрой N-Puzzle (также известной как 15-головоломка ...), где вы разбиваете изображение на квадратной сетке, удаляете одну часть и перемешиваете.Меня не интересуют решения головоломки, так как это зависит от пользователя.Но я хотел бы псевдослучайно перетасовать доску.

Я знаю, что половина всех возможных перетасовок сделает доску неразрешимой.Существует ли простой способ псевдослучайного генерирования перемешанного состояния, если у меня есть некоторая функция rand () - esc и я знаю размер доски?

У меня игровая доска в памяти, многомернаямассив целых чисел.Мой метод просто размещает изображения в обратном порядке, переключая последнее с последнего на последнее изображение на четных досках.Моя текущая функция ниже, и я работаю на Java.

private void shuffle()
{
    gameState = new int[difficulty][difficulty];
    int i = 0, N = (difficulty * difficulty) -1;

    while (i < N)
        gameState[(int)(i / difficulty)][i % difficulty] = N - ++i;
    gameState[difficulty-1][difficulty-1] = N;

    // N id even when the remainder of N/2 is 0
    if ((difficulty % 2) == 0)
    {
        // swap 2nd to last and 3rd to last element
        int tmpEl = gameState[difficulty-1][difficulty-2];
        if (difficulty == 2)
        {
            gameState[1][0] = gameState[0][1];
            gameState[0][1] = tmpEl;
        }
        else
        {
            gameState[difficulty-1][difficulty-2] = gameState[difficulty-1][difficulty-3];
            gameState[difficulty-1][difficulty-3] = tmpEl;
        }
    }
}

Answer 1

Эта проблема в основном сводится к выполнению стандартного алгоритма тасования с небольшим поворотом.

Ключевое наблюдение состоит в том, что для решения 15-пазла четность перестановки и четность пустого квадрата должны быть одинаковыми.

Сначала создайте случайную перестановку, используя для этого стандартный алгоритм. Например, алгоритм Кнута тасования: Случайные перестановки

Преимущество использования тасования Кнута (или тасования Фишера-Йейтса) заключается в том, что оно включает в себя обмен числами, что позволяет легко отслеживать четность перестановки. Каждый своп либо сохраняет паритет (если вы поменяли местами 1 и 3), либо изменяет паритет (если вы поменяли местами 1 и 2).

Поместите пустой квадрат в ту же четность, что и четность перестановки, и все готово. Если перестановка имеет нечетную четность, тогда поместите пробел в нечетный квадрат (1,3,5, ... выбранный случайным образом). Если перестановка имеет четную четность, поместите пробел на четный квадрат.

Answer 2

Мое предложение будет отслеживать пустой квадрат в массиве (кусок, который вы удалили).
Затем выберите случайную сторону этого пустого квадрата (обязательно сделайте необходимые проверки границ) и «поменяйте» часть на этой стороне с пустым квадратом. Это имитирует скользящее действие, которое будет делать игрок.
Повторите это действие несколько раз (простая настройка сложности - сложность устанавливает количество итераций, которые вы делаете), каждый раз «скользя» по пустому квадрату по всему массиву.

С помощью этого метода вам просто нужно отследить, где находится пустой квадрат, а затем выбрать случайную сторону для перемещения.

Надеюсь, это немного вам поможет - я не предоставляю здесь никакого кода, просто простой алгоритм для работы с вами.

Answer 3

Просто генерируйте случайные головоломки, пока вы не создадите один с четным паритетом.http://heuristicswiki.wikispaces.com/N+-+Puzzle