Prolog - problem konika szachowego

Question

Witam serdecznie, muszę napisać program w Prologu rozwiązujący problem konika szachowego.
Konik musi odwiedzić każde pole, ale na każdym polu może stanąć tylko 1 raz.
Na razie mam tyle (kod poniżej), teraz powinienem skorzystać chyba z listy, żeby zapamiętać na których polach konik już był, ale właśnie mam z tym problem.

move(X, Y, Xmax, Ymax) :-
X + 1 < Xmax,
Y + 2 < Ymax,
A is X + 1,
B is Y + 2,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move(X, Y, Xmax, Ymax) :-
X + 2 < Xmax,
Y + 1 < Ymax,
A is X + 2,
B is Y + 1,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move(X, Y, Xmax, Ymax) :-
X + 2 < Xmax,
Y - 1 >= 0,
A is X + 2,
B is Y - 1,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move(X, Y, Xmax, Ymax) :-
X + 1 < Xmax,
Y - 2 >= 0,
A is X + 1,
B is Y - 2,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move(X, Y, Xmax, Ymax) :-
X - 1 >= 0,
Y - 2 >= 0,
A is X - 1,
B is Y - 2,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move[X, Y, Xmax, Ymax) :-
X - 2 >= 0,
Y - 1 >= 0,
A is X - 2,
B is Y - 1,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move(X, Y, Xmax, Ymax) :-
X - 2 >= 0,
Y + 1 < Ymax,
A is X - 2,
B is Y + 1,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

move(X, Y, Xmax, Ymax) :-
X - 1 >= 0,
Y + 2 < Ymax,
A is X - 1,
B is Y + 2,
write('X='), write(A),
write('Y='), write(B), nl,
move(A, B, Xmax, Ymax).

 

Answer 1

robiłem coś takiego w VBA. sprawę rozwiązałem w ten sposób:

Założenia:

1) bazowo konik może wykonać 8 ruchów z danego pola (z niektórych mniej)

2)konik musi wiedzieć, gdzie był, gdzie nie może skoczyć i jak może się "cofnąć"

3) konik zawsze próbuje skoczyć w tej samej kolejności - wariant skoku, 8 możliwości(1 skok -góra,lewo, 2 skok - góra,prawo, 3 skok prawo,góra itp.)

 do zadania użyłem 2 tablic:

1 - odzwierciedlająca szachownicę (wszędzie wartości ustawione na 0) oraz dodatkowy margines 2 pól z każdej strony ( wartość ustawiona na 100). szachownica będzie zapisywała numer skoku konika (a jednocześnie numer inny niż 0 będzie oznaczał, że konik już dane pole odwiedził, stąd marginesy - żeby konik nie wyskoczył za szachownicę).

2-  64 elementowa tablica z numerem wariantu skoku (indeks tablicy jest za razem numerem skoku)

jak sprawa wygląda.:

 konik jest w pozycji x,y. w tej pozycji zostaje zapisany numer skoku.

 konik sprawdza czy pierwszy wariant skoku jest możliwy, jeżeli tat to do wariantu skoku pod nr 1 zostaje wprowadzona wartość 1, jeżeli nie sprawdza, czy może użyć drugiego wariantu i tak az do wariantu nr 8.

 

jeżeli nie przeskoczył wszystkich pól a warianty się skończyły cofa się krok wstecz (np w poprzednim kroku wybrany został wariant skoku 4) i stara się użyć następnego wariantu skoku (tutaj nr 5).

konik będzie wykonywał kolejne kroki w przód i wstecz aż obskoczy wszystkie pola, lub sprawdzi wszystkie warianty (nie zawsze będzie możliwe wypełnienie całej szachownicy)