От решения 8-Queens к более общему решению n-Queens на Prolog

Я изучаю Пролог в качестве универсального экзамена, и у меня возникли проблемы со следующим упражнением.

У меня есть следующее классическое решение проблемы 8-ферзей (и это не проблема для меня). Изменяя это решение, я должен создать новое решение для более общей проблемы n-Queens, которая обрабатывает переменное количество ферзей.

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,       % Q e Q1 sono su righe diverse
                      % Q e Q1 sono su diagonali diverse:
                      Y1-Y =\= X1-X,
                      Y1-Y =\= X-X1,
                      % Q non attacca regine nella sottolista Others:
                      noattack( X/Y, Others).

% TEMPLATE DELLE SOLUZIONI: c'è una regina su ogni colonna:
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

Хорошо, эта программа выглядит довольно просто: у меня есть список королев, у которых они не должны атаковать друг друга.

Если список ферзей пуст, вероятность того, что ферзь атакует другого ферзя в списке, отсутствует, поэтому пустой список является решением проблемы (это базовый вариант решения)

* Если список ферзей не пуст, я могу разделить его на [X / Y | Others], где X / Y - текущая позиция на доске первого ферзя в списке * (позиция rappresentend парой (X, Y), где X - столбец, а Y - линия)

Итак, ИСТИНА, что список [X / Y | Others] является РЕШЕНИЕМ проблемы, если верны следующие соотношения:

  1. Подсписок Others сам по себе является решением (другие не содержат ферзя, который атакует другого ферзя в списке)

  2. Y принадлежит целому числу от 1 до 8 (потому что у меня 8 строк)

  3. Первая ферзь в списке не атакует других ферзей в подсписке Others

Затем определяется отношение noattack, которое указывает, когда я могу сказать, что это правда, что ферзь не атакует другого ферзя (это довольно просто: они не могут оставаться на той же линии, на тот же столбец, на той же диагонали)

Наконец, у меня есть шаблон решения, который упрощает мою жизнь, ограничивая значение X значением от 1 до 8 (потому что я знаю, что 2 ферзя не могут оставаться на одних и тех же столбцах ... поэтому каждая ферзь в решение остается в столбце, отличном от всех остальных ферзей)

Поэтому я думаю, что самая большая проблема - в строке, в которой я указываю количество столбцов:

member(Y,[1,2,3,4,5,6,7,8])

и в строке, в которой я определяю шаблон решения:

template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

Я понятия не имею, как расширить предыдущее решение для обработки переменного количества ферзей.


prolog n-queens
person AndreaNobili    schedule 05.04.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

кажется легким, обойдя размер:

solution(_, []).
solution(N, [X/Y|Others]) :-
    solution(N, Others),
    between(1, N, Y),
    noattack(X/Y, Others).

noattack(_,[]).
noattack(X/Y, [X1/Y1 | Others]) :-
    Y =\= Y1,       % Q e Q1 sono su righe diverse
    Y1-Y =\= X1-X,  % Q e Q1 sono su diagonali diverse
    Y1-Y =\= X-X1,
    noattack( X/Y, Others). % Q non attacca regine nella sottolista Others

% TEMPLATE DELLE SOLUZIONI: c'è una regina su ogni colonna:
template(N, L) :-
    findall(I/_, between(1,N,I), L).

тестовое задание:

?- N=6, template(N, L), solution(N, L).
N = 6,
L = [1/5, 2/3, 3/1, 4/6, 5/4, 6/2] ;
N = 6,
L = [1/4, 2/1, 3/5, 4/2, 5/6, 6/3] ;
N = 6,
L = [1/3, 2/6, 3/2, 4/5, 5/1, 6/4] ;
N = 6,
L = [1/2, 2/4, 3/6, 4/1, 5/3, 6/5] ;
false.

(Я должен его нарисовать, чтобы сказать, нормально ли ...)

person CapelliC    schedule 05.04.2013
comment
Tnx так много. Спасибо за помощь и за уделенное время. У меня есть только два хороших мнения о том, как это работает: - person AndreaNobili; 06.04.2013
comment
1) Чтобы быть верным, что решение (N, [X / Y | Others]) (список [X / Y | Others], состоящий из N ферзей, является решением), вы добавляете, что должно быть истинным, что: между (1, N , Y) вместо члена (Y, [1,2,3,4,5,6,7,8]). Это просто день, когда Y (количество столбцов) должно быть ›1 и‹ N. Глядя на ссылки, я думаю, что Y это переменная, поэтому при каждом рекурсивном вызове решения она привязывается ко всем целым числам от 1 до N, где N - это номер столбца в рассматриваемой подзадаче. Это правда? - person AndreaNobili; 06.04.2013
comment
2) Второе сомнение связано с тем, как вы создаете шаблон решения в случае N ферзей ... Я думаю, что его смысл аналогичен шаблону удержания, в котором у меня был список вроде: [1 / Y1,2 / Y2 , ...., 8 / Y8]. Но в этом случае у меня не может быть статического списка, но список должен быть создан с переменным количеством позиций (N позиций). Итак, вы делаете: template (N, L): - findall (I / _, между (1, N, I), L). но что именно значит? Я думаю, что findall создает динамически список ... список состоит из пары (X, Y), где X представляет индекс строки, а Y - индекс столбца. - person AndreaNobili; 06.04.2013
comment
Хорошо ... как в старом примере с 8 ферзем, у меня есть список шаблонов (созданный с помощью findall? Это правильно?), Что каждая ферзь находится на другой линии, поэтому у меня есть, что каждая ферзь находится в позиции I / _, где я число от 1 до N (так что, если N = 3, у меня есть список шаблонов вроде [1 / _, 2 /, 3 / _]. Есть сомнения: почему значение Y равно _, а не Y? И вторые сомнения: Я так много представил список, созданный findall? Tnx - person AndreaNobili; 06.04.2013
comment
1) в Прологе у нас есть отношения, и бывает, что и member / 2, как вы его написали, и между / 3 обозначают одно и то же отношение. Можно было использовать numlist(1, N, L), member(Y, L), но, насколько мне известно, я предпочитаю более простые решения. 2) каждый _, приводящий к выходному списку findall, является независимым, точно так же, как Y1, Y2 и т. Д., И их основная цель заключается в том, чтобы «свободные» слоты оценивались поиском. Так что findall / 3 удобен. Это «понимание списка» Пролога .... - person CapelliC; 06.04.2013