Форум программистов, компьютерный форум, киберфорум
Наши страницы
Prolog
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Quadra
10 / 10 / 0
Регистрация: 29.04.2013
Сообщений: 141
#1

SWI-Prolog, Шахматная задача, Конь

13.02.2016, 17:26. Просмотров 896. Ответов 5
Метки нет (Все метки)

Доброго времени суток. Столкнулся с "классической" задачей, о которой все говорят которую все знают, но упорно прячут решение. Итак:

Задача о конях. Задача состоит в отыскании всех расстановок максимально возможного количества коней на пустой шахматной доске (NxN), таких, в которых ни один из коней не находится под боем другого.

Собственно, вариация задачи о 8 Ферзях, решений которой довольно много, как и решений задачи о Ладьях. При этом, что одна, что вторая, не вызывают особых сложностей в описании возможных ходов. Но как быть с этим животным?

Очевидно, что максимальное число коней равно N*N/2. И все фигуры будут стоять либо на черных клетках, либо на белых. В силу своей бездарности в прологе у Братко была взята программа, решающая задачу о Ферзях:
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
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]).
И предпринята попытка переделать её под коней, а именно, изменить функцию noattack() (для N=4 и 8 коней, ибо для N=8 все 32 коня не умещаются на экране вывода, просто скрываются под многоточием после восьмого элемента, как выводить больше, кстати?):
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]).
Но пролог со мной не согласился. Что не так?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2016, 17:26
Ответы с готовыми решениями:

Задача на Swi-Prolog
Здравствуйте. В общем появилась проблема. Никогда не изучал пролог. И вот дали...

Задача SWI prolog
Подскажите, пожалуйста, как можно решить эту задачу? База данных содержит...

Логическая задача на SWI Prolog
Задали решить логическую задачу посредством языка пролог, лог задачи: На...

Логическая задача swi prolog
База данных содержит факты вида ученик(имя, класс) и увлекается(имя, хобби)....

Задача со списками (SWI-Prolog)
Доброго времени суток, Есть 2 задачи на списки: 1. Разделить список на две...

5
Black Fregat
2447 / 1253 / 339
Регистрация: 31.05.2009
Сообщений: 4,915
15.02.2016, 07:55 #2
Цитата Сообщение от Quadra Посмотреть сообщение
как выводить больше, кстати?):
Самое простое, что Вы можете сделать - вывести результат самостоятельно, в таком виде, в каком нужно.

Или же нужно переключать флаги Пролога. Попробуйте ввести в консоли перед запуском
Prolog
1
set_prolog_flag(answer_write_options,[]).
Цитата Сообщение от Quadra Посмотреть сообщение
Что не так?
Что сходу не так - так это разделение веток внутри предиката noattack запятыми. Чтобы получилось ИЛИ, ветки должны разделяться точкой с запятой.

Но, боюсь, "в лоб" переделать решение для ферзей под коней не получится: все известные мне решения для ферзей последовательно перебирают горизонтали, явно используя невозможность размещения двух ферзей на одной горизонтали. С конями перебор должен быть более "тупым"..
0
Quadra
10 / 10 / 0
Регистрация: 29.04.2013
Сообщений: 141
15.02.2016, 13:38  [ТС] #3
Цитата Сообщение от Black Fregat Посмотреть сообщение
Что сходу не так - так это разделение веток внутри предиката noattack запятыми. Чтобы получилось ИЛИ, ветки должны разделяться точкой с запятой.
Но, боюсь, "в лоб" переделать решение для ферзей под коней не получится: все известные мне решения для ферзей последовательно перебирают горизонтали, явно используя невозможность размещения двух ферзей на одной горизонтали. С конями перебор должен быть более "тупым"..
ИЛИ пробовал. Там тоже ничего не получается.

Весь перебор, по сути, сводится к двум вариантам: заполнять каждую строку через одну позицию начиная с первой позиции в строке, либо со второй. Но как это реализовать в прологе идей нет совершенно. Была идея вроде объявить белые и черные клетки, а потом заставить пролог выставлять фигуру только на белые или только на черные, но это как-то тупо, что ли.
0
arlat
358 / 358 / 68
Регистрация: 07.10.2013
Сообщений: 793
15.02.2016, 14:46 #4
Здесь про коня, дойти из одной клетки в другую, можно почерпнуть что-то и для задачи расстановки
Движение коня по шахматной доске
0
Миниатюры
SWI-Prolog, Шахматная задача, Конь  
Quadra
10 / 10 / 0
Регистрация: 29.04.2013
Сообщений: 141
25.03.2016, 20:02  [ТС] #5
Решение на Visual Prolog. На ввод подаётся размер поля. Тему можно закрывать.
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
domains
    list=integer*
predicates
    member(integer,list)
    solution(integer,list,list,list)
    noattack(integer,integer,list,list)
    attack(integer,integer,integer,integer)
    gen(integer,integer,list)
    run
clauses 
    run:-write("Size: "),readint(Size),Knights=Size*Size/2,gen(1,Size,SizeList),
    solution(Knights,X,Y,SizeList),write("Positions X: "),write(X),nl,write("Positions Y: "),write(Y),nl.
    
    solution(0,[],[],_).
    solution(Knights,[X|XTail],[Y|YTail],SizeList):-M=Knights-1,solution(M,XTail,YTail,SizeList),
    member(X,SizeList),member(Y,SizeList),noattack(X,Y,XTail,YTail).
    
    noattack(_,_,[],[]).
    noattack(X,Y,[X1|XTail],[Y1|YTail]):-X>X1,noattack(X,Y,XTail,YTail),not(attack(X,Y,X1,Y1)).
    noattack(X,Y,[X1|XTail],[Y1|YTail]):-X=X1,Y>Y1,noattack(X,Y,XTail,YTail),not(attack(X,Y,X1,Y1)).
    
    attack(X,Y,X1,Y1):-X1=X+1,Y1=Y+2.
    attack(X,Y,X1,Y1):-X1=X-1,Y1=Y+2.
    attack(X,Y,X1,Y1):-X1=X+1,Y1=Y-2.
    attack(X,Y,X1,Y1):-X1=X-1,Y1=Y-2.
    attack(X,Y,X1,Y1):-X1=X+2,Y1=Y+1.
    attack(X,Y,X1,Y1):-X1=X-2,Y1=Y+1.
    attack(X,Y,X1,Y1):-X1=X+2,Y1=Y-1.
    attack(X,Y,X1,Y1):-X1=X-2,Y1=Y-1.
    
    member(Y,[Y|_]).
    member(Y,[_|YTail]):-member(Y,YTail).
    
    gen(N,N,[N]).
    gen(N1,N2,[N1|List]):-N1<N2,M=N1+1,gen(M,N2,List).
goal
    run.
0
arlat
358 / 358 / 68
Регистрация: 07.10.2013
Сообщений: 793
30.03.2016, 13:54 #6
Цитата Сообщение от Quadra Посмотреть сообщение
о которой все говорят которую все знают, но упорно прячут решение
никто не прятал - я ссылку дал, там даже прям оттуда ничего не меняя запустить
Prolog
1
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]).
и то уже понятно, что дальше надо делать
0
Миниатюры
SWI-Prolog, Шахматная задача, Конь  
30.03.2016, 13:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2016, 13:54

Списки в SWI-Prolog. Задача
Добрый день! Помогите, пожалуйста, решить задачу на SWI-Prolog. Задание:...

Задача сетевого планирования SWI Prolog
Написал программу из книги Ивана Братко по решению задачи сетевого...

Задача Прима-Краскала (SWI-Prolog)
Дана страна (плоская и в ней n городов). Нужно соединить города телефонной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru