Mam do napisania na zaliczenie program rozwiązujący problem skoczka na standardowej szachownicy 8x8. Napisałem prosty rekurencyjny brute force, jednak algorytm jest wolny (pierwsze rozwiązanie znajduje w pare minut na procku 2 GHz), a moja ambicja celuje w coś lepszego.
Problem polega na tym, aby przejść przez wszystkie pola poruszając się ruchem konika szachowego tak, aby na każdym polu stanąć dokładnie jeden raz. Szachownice i możliwe ruchy można przedstawić za pomocą nieskierowanego nieważonego grafu o 64 wierzchołkach, a problem sprowadza się do znalezienia ścieżki Hamiltona w tym grafie.
Znacie jakiś konkretny algorytm rozwiązania tego problemu. Zapewne ktoś już się zajmował tym problemem - jak go rozwiązaliście ? Jakie są wasze sugestie ?
na razie znalazłem to, jednak kod jest bardzo rozległy, pisany w c i ciężko się go czyta. Trudno wyłapać punkty kluczowe algorytmu.