Fifteen puzzle

Na początku kilka słów czym jest gra piętnastka:

Gra 15-puzzle zostala wynaleziona pod koniec XIX wieku przez Sam Loyd, jednego z najwiekszych tworcow roznorakich ukladanek. Poczatkowo zostala nazwana "Boss puzzle", pozniej zmieniono nazwe na "15-puzzle". Zasadniczo gra polega na tym, aby wymieszac klocki, a nastepnie przywrocic ustawienie poczatkowe. Plansza jest wymiarów 4x4, wiec jedno pole zawsze pozostanie puste. Przesuwajac klocki na puste pole trzeba tak manewrowac, aby ustawic calosc w zadanej kolejnosci. Dla niektorych ustawien poczatkowych rozwiazanie jest mozliwe, dla innych nie. Jednakze jezeli ustawienie poczatkowe zostalo wygenerowane przez przesuwanie klockow rozwiazanie zawsze jest osiagalne. Dla rozstawienia losowego nie musi tak byc. W kazdym momecnie mamy przynajmniej dwie mozliwosci ruchu (w naroznikach), trzy przy scianach, oraz cztery wewnatrz.

Planszę 4x4 wczytywana jest z pliku / klawiatury / losowana przez program oraz przechowywana za pomocą vectora vectorów. Te funkcje już mam. Muszę napisać funkcję który rozwiąże układankę za pomocą algorytmu przeszukiwania grafu - DFS/BFS (wyświetlić rozwiązanie w postaci korków: lewo, prawo, góra, dół). Ma to wyglądać w ten sposób, że wchodząc do jednego węzła sprawdzamy czy jest jest stanem wzorcowym, jeśli nie generujemy wszystkie możliwe do zrobienia kroki, dla każdego dziecka robimy to samo itd.

Korzeń:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

Dzieci:

1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12

1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15

I tak dalej. Nie mam pojęcia w jaki sposób mam przechowywać określone stany.

na liczbę 0-15 potrzeba 4 bitów, pól masz 16, w sumie daje to 64 bity, więc jeśli chcesz przechowywać wszystkie przeanalizowane stany to lista long logn int powinna być wystarczająca.

PS. Nie zapomnij, że powinieneś sprawdzać, że nowy stan już sprawdzałeś/odwiedziłeś, bo inaczej skończysz z nieskończoną rekurencją.

Pytanie czy za każdą zmianą stanu kopiować wszystkie elementy do nowego vectora?

jeśli chcesz szybko porównywać, czy już odwiedziłeś dany stan to trzymanie tego stanu jako różnicy będzie zbyt kłopotliwe. Napisałem ci przecież, że do pełnego opisu stanu wystarczy liczba 64 bitowa, więc nie ma co się zastanawiać czy trzymać pełną informację czy częściową.

Dla szybkości algorytmu będzie miało znaczenie, czy stany przechowujemy za pomocą vector <vector < int > > zamiast vector < int > ?

Tak. Będziesz przechowywał kopie kopii z czego będzie musiało być dwa razy kopiowane

Przepisałem algorytm BFS, tak aby zamiast vectora vectorow operowal na jednym vectorze.

 // Algorytm BFS
void bfs(int rozmiar_planszy, vector < long long int > &tabela, vector < long long int > &wzor, char porzadek[])
{
     list < vector < long long int > > do_sprawdzenia;
     list < vector < long long int > > sprawdzone;
     do_sprawdzenia.push_back(tabela);
     
     clock_t s, f;
     double czas=0;
     s = clock();
     int stany_powtorzone = 0;
     while(do_sprawdzenia.size() !=0)
     {
           vector < long long int > kopia;
           kopia = do_sprawdzenia.front();
           do_sprawdzenia.pop_front();
           
           if(kopia == wzor)
           {
                    f = clock();
                    czas = (double)(f - s) / (double)(CLOCKS_PER_SEC);
                    cout << "Znaleziono rozwiazanie!" << endl;
                    cout << "Dlugosc kolejki do_sparwdzenia: " << do_sprawdzenia.size() << endl;
                    cout << "Dlugosc kolejki sprawdzone: " << sprawdzone.size() << endl;
                    cout << "Stany odrzucone: " << stany_powtorzone << endl << endl;
                    cout << "Czas wykonania algorytmu: " << czas << endl;
                    system("PAUSE");
           }
           else
           {
                    sprawdzone.push_back(kopia);
                    int pozycja_zero = znajdz_zero(rozmiar_planszy, kopia);
                    
                    for(int i = 0; i < 4; i++)
                    {
                            char znak = porzadek[i];
                            vector < long long int > i;
                            i = kopia;
                            if(znak == 'D')
                                    ruch_dol(rozmiar_planszy, pozycja_zero, i);
                            if(znak == 'G')
                                    ruch_gora(rozmiar_planszy, pozycja_zero, i);
                            if(znak == 'P')
                                    ruch_prawo(rozmiar_planszy, pozycja_zero, i);
                            if(znak == 'L')
                                    ruch_lewo(rozmiar_planszy, pozycja_zero, i);
                            bool czy_odwiedzony = sprawdz_listy(do_sprawdzenia, sprawdzone, i);
                            if(czy_odwiedzony == false)
                            {
                                    do_sprawdzenia.push_back(i);
                            }
                            else
                            stany_powtorzone = stany_powtorzone + 1;
                    }
           }
     }
}

Pytanie tylko, w jak sposób zmodyfikować go tak by na końcu wyświetlał ścieżkę (typu LDPG), w jakiej dotarł od stanu początkowego do stanu końcowego?

EDIT: Zaktualizowałem kod.

Nie wiem czy się dobrze rozumiemy. Jeden stan przechowywany jest w jednym vectorze. Elementami vectora są liczny od 1 do 15 oraz 0. Po co więc korzystać z tylu long long int? Dla przykładu podam funkcję wczytującą plansze:

void wczytaj_vector(int rozmiar_planszy, vector < long long int > & plansza)
{
     cout << "Wczytywanie planszy: " << endl;
     for(int i = 0; i < rozmiar_planszy * rozmiar_planszy; i++)
     {
          cin >> plansza[i];
     }
} 

Tak jak napisałem do opisu stanu (węzła grafu) możesz użyć long long int (64 bity - każde kolejne 4 bity opisują numer klocka). Ta dana jest bardziej kompaktowa niż vector<int> i o wile szybsza do porównania czy odwiedziłeś już dany stan.
Oszczędzisz na pamięci i na szybkości sprawdzania czy stan (węzeł grafu) już został sprawdzony.

Teraz pozostało jeszcze odkładanie drogi. Myślałem żeby utworzyć np. klasę stan, której składnikami będzie:

• vector < long long int > stan
• char kierunek

W zmiennej stan przechowywać plansze, a w zmiennej kierunek ruch z jakiego została utworzona. W momencie gdy program znajdzie stan wzorcowy (wszystkie sprawdzone odkłada do listy stany_odiwedzone), algorytm zacznie się wracać - odłoży na liście droga kierunek z którego został otrzymany stan wzorcowy, na tej podstawie wygeneruje stan wcześniejszy, znajdzie go w liście stany_odwiedzone, sprawdzi z jakiego kierunku ten został utworzony, wygeneruje go i operacja będzie powtarzana dopóki nie osiągnie stanu początkowego. Pytanie tylko czy można ten cel osiągnąć w prostszy sposób?

Poco ci odtwarzać stan wcześniejszy z ruchu skoro masz go już zapisanego w poprzednim elemencie tablicy?

W przypadku algorytmu DFS, tak wszystko jest we wcześniejszych elementach. W przypadku BFS'a jednak nie.

Żadnych pomysłów?