Как правильно перемешать пятнашки, чтобы их можно было собрать?

Question

Пытаюсь написать игру "Пятнашки". В массиве у меня находится такая запись:

{ "1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","_" }

Простое перемешивание может привести к тому, что комбинация - не будет иметь решения. Как правильно перемешивать, чтобы таких ситуаций не случалось?

Моя попытка кода:

#include <iostream>
using namespace std;
int main() {
    int a[16]={1,2,3,4,5,6,7,8,9,10,11,12,13,15,14,0};//нерешаемая ситуация
    int inv=0;
    for(int i=0; i<16; ++i)
        if(a[i])
            for(int j=0; j<i; ++j)
                if(a[j]>a[i])
                    ++inv;
    for(int i=0; i<16; ++i)
        if(a[i]==0)
            inv += 1 + (i/4);
    puts((inv & 1) ? "NoSol" : "SolEx");
    return 0;
}

Первый цикл вычисляет количество инверсий. Второй цикл вычисляет где, находится пустая клетка.

Answer 1

Как правильно написал @Harry - один из вариантов погонять случайным образом пустую клетку. Для наглядности можно использовать не одномерный массив, а двумерный - поле пятнашек 4x4. Начальное состояние:

int a[4][4] = {
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9,10,11,12},
{13,14,15, 0} };

Теперь датчиком случайных чисел выбираете направление и двигаете ноль. Например вверх - меняете 0 и 12 местами. Потом влево и ещё раз влево. Получается:

{ 1, 2, 3, 4},     { 1, 2, 3, 4},     { 1, 2, 3, 4},
{ 5, 6, 7, 8}, =>  { 5, 6, 7, 8}, =>  { 5, 6, 7, 8},
{ 9,10,11, 0},     { 9,10, 0,11},     { 9, 0,10,11},
{13,14,15,12}      {13,14,15,12}      {13,14,15,12}

И так сотню раз. Поскольку ходы все корректные, результат тоже корректный.

БЛОГ НА HUSL

Как правильно перемешать пятнашки, чтобы их можно было собрать?

Ответы (1 шт):