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.