SWI-Prolog, Шахматная задача, Конь
Формулировка задачи:
Доброго времени суток. Столкнулся с "классической" задачей, о которой все говорят которую все знают, но упорно прячут решение. Итак:
Задача о конях. Задача состоит в отыскании всех расстановок максимально возможного количества коней на пустой шахматной доске (NxN), таких, в которых ни один из коней не находится под боем другого.
Собственно, вариация задачи о 8 Ферзях, решений которой довольно много, как и решений задачи о Ладьях. При этом, что одна, что вторая, не вызывают особых сложностей в описании возможных ходов. Но как быть с этим животным?
Очевидно, что максимальное число коней равно N*N/2. И все фигуры будут стоять либо на черных клетках, либо на белых. В силу своей бездарности в прологе у Братко была взята программа, решающая задачу о Ферзях:
И предпринята попытка переделать её под коней, а именно, изменить функцию noattack() (для N=4 и 8 коней, ибо для N=8 все 32 коня не умещаются на экране вывода, просто скрываются под многоточием после восьмого элемента, как выводить больше, кстати?):
Но пролог со мной не согласился. Что не так?
Листинг программы
- solution([]).
- solution([X/Y | Others]) :- solution(Others), member(Y,[1,2,3,4,5,6,7,8]),
- noattack(X/Y, Others).
- noattack(_, []).
- noattack(X/Y, [X1/Y1 | Others]) :-
- Y =\= Y1,
- Y1-Y =\= X1-X,
- Y1-Y =\= X-X1,
- noattack(X/Y, Others).
- member(Item, [Item | Rest]).
- member(Item, [First | Rest]) :- member(Item, Rest).
- template([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y9]).
Листинг программы
- solution([]).
- solution([X/Y | Others]) :- solution(Others), member(Y,[1,2,3,4]),
- noattack(X/Y, Others).
- noattack(_, []).
- noattack(X/Y, [X1/Y1 | Others]) :-
- ((X=\=X1+1 , Y=\=Y1+2),
- (X=\=X1+2 , Y=\=Y1+1),
- (X=\=X1+2 , Y=\=Y1-1),
- (X=\=X1+1 , Y=\=Y1-2),
- (X=\=X1-1 , Y=\=Y1-2),
- (X=\=X1-2 , Y=\=Y1-1),
- (X=\=X1-2 , Y=\=Y1+1),
- (X=\=X1-1 , Y=\=Y1+2)),
- noattack(X/Y, Others).
- member(Item, [Item | Rest]).
- member(Item, [First | Rest]) :- member(Item, Rest).
- template([1/Y1, 2/Y2, 3/Y3, 4/Y4, 1/Y5, 2/Y6, 3/Y7, 4/Y8]).
Решение задачи: «SWI-Prolog, Шахматная задача, Конь»
textual
Листинг программы
- between(1, 8, X), between(1, 8, Y), between(1, 8, X1), between(1, 8, Y1), not([X,Y]=[X1,Y1]), move_chess_figure(Figure, [X, Y], [X1, Y1]).
Объяснение кода листинга программы
- Между 1 и 8 находится переменная X.
- Между 1 и 8 находится переменная Y.
- Между 1 и 8 находится переменная X1.
- Между 1 и 8 находится переменная Y1.
- Переменные X и Y не равны X1 и Y1.
- Выполняется ход фигуры на шахматной доске, где Figure - это название фигуры, [X, Y] - начальное положение фигуры, [X1, Y1] - конечное положение фигуры.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д