Читая учебник, по проблемам искусственного интеллекта, захотелось поиграться с Прологом против N-ферзей.
Когда-то PROLOG уберёг меня от плохого влияния бейсика. Даже объектно-ориентированное проектирование не смогло вырвать меня, из цепких оков императивного мышления.
До знакомства с Прологом, я смутно понимал что класс это код, а объект это данные. Шаблоны функций или классов были неприступной крепостью. Метоклассы ― магия. От элементов функционального программирования сводило зубы.
Пролог помог поставить эти парадигмы программирования на единый фундамент. Теперь (спустя много лет), играясь с ферзями, мне стало понятно, почему у него это получилось.
Пытаясь одолеть ферзей, вроде пишу прологовский код, но у меня возникает ощущение, что на самом деле я делаю пометки своих размышлений. Мысли плавно застывают в предикатах. Программа чудным образом повторяет дерево анализа задачи.
Разуму удобно думать, разглядывая код Пролога. Эти предикаты, то как они связаны между собой, структуры фактов, возня с переменными ― все это помогает размышлять о задаче.
Может быть потому что француз Alain Colmerauer создал PROLOG по образу и подобию разума? Конечно, Прологу далеко до разума, но некое родство ощущается. И это хорошо заметно на комбинаторных задачах.
Разум думает ― решает комбинаторную задачу. Пролог ищет цель ― решает комбинаторную задачу.
Только у разума колоссальное превосходство в качестве и колличестве эвристик, а PROLOG: гол, как сокол. Лишь хиленькая прологовская машинка, работающая на принципах поиска в графе AND/OR.
Что у Пролога, что у разума, на комбинаторных задачах, эвристики сильно сокращают время поиска решения.
Одно дело вычислять на пальцах:
Другое дело, знать ответ зарание:
Мозг содержит безумное количество эвристик-знаний. Это помогает разуму, мгновенно решать задачи, избегая комбинаторного взрыва, против которого у него есть оружие. Cпособность обобщать новые знания, поступившие в мозг, с уже существующими эвристиками, пересматривая и уточняя их.
Наверное гении понимают это и умеют целенаправлено накачивать мозг информацией так, чтобы разум обобщал эвристики там, где гению нужно решить титаническую задачу.
Известные задачи, разум гения решает быстро. На новых задачах, в условиях жесткой нехватки информации, разум гения умудряется разглядеть решение там, где обычный, не треннированный разум, даже и не подумал бы искать.
Я не гений, тем более не был им, на заре карьеры, когда познакомился с Прологом. Однако теперь понимаю, что дал Пролог. Он дал возможность разуму, разглядеть эвристику, позволяющую эффективно анализировать задачи, производить их оптимальную декомпозицию, вплоть до написания «совершенного кода».
Вот тебе и тренажёр разума. Можно возразить, что любой язык программирования способен тренировать разум. Однака, такой потрясающий резонанс, у меня получился только с PROLOG-ом.
Поставив SWI-Prolog, я неторопливо настроил Eclipse.
Читать описание задачи и рассматривать готовый код, не поможет разуму сформировать навыки по анализу и декомпозии задачи. О написание кода я молчу. Поэтому я буду практиковаться, предворительно сформулировав цели.
Супер цель: разум должен обобщать, полученные знания, с тем, что уже находится в моей профессиональной памяти.
Цель: написать программу, которая как можно быстрее находит все верные варианты расстановки n-ферзей. Потом сравнить её с Ocaml-овским вариантом.
NP-комбинаторная задача об эн-ферзях решается перебором в глубину с возвратом. К примеру, для 4-х ферзей существует 4! = 24 варианта растановки, из которых только две дают решение.
Рассматривая дерево задачи, я понимаю, что перебирать все перестановки нет смысла. Нужна использовать эвристику, которая осечёт ветки дерева, не содержащие решения.
С чистой совестью, подглядываю в книгу Ивана Братко. Мне везёт как никогда. Оказывается задача о ферзях очень популярна, в образовательных целях. У Братко есть три варианта (CLP не в счёт), которые я опишу в порядке медленности исполнения.
Исходные коды переписаны для шахматных досок произвольного размера и адаптированы для пакетных опытов.
Листинг файла «bratko-1.pl».
Предикат solution лаконичен. За такую выразительную краткость, программа выполняется дольше всего. PROLOG просматривать все N! вариантов.
Код использует только Y координаты клеток.
При рассмотрении кода, я обратил внимание, на интересное поведение предиката permutation. Код предиката находиться в библиотечном модуле «lists.pl».
Ожидаемое поведение предиката это получение всех перестановок входящего списка [0, 1, 2]:
Пролог выдал первый вариант, из всех возможных.
Просим прологовскую машину, выдать все перестановки:
Похоже, начинаю понимать отличие предиката от функции. Но для ясности, пробую задать такие вопросы:
Пролог ответил как истинный программист: точно, но бесполезно.
Что интересно, предикат permutation ведет себя симметрично, относительно своих переменных.
Листинг файла «bratko-2.pl».
Вариант пошустрее, уже используется поиск в глубину с возвратом.
Для обозначения клетки используется структура X/Y, где оператор / объединяет два атома. Опыт показывает, что по скорости выполнения, это выгодный способ кодирования клетки, по сравнениею с [X, Y].
У предиката solution переменная Queens исходящая. Поэтому сначала происходит рекурсивное углубление, и только потом происходит вычисление элемента списка.
По другому работает со списком предикат noattack. У него переменная Queens входящая. Сначало происходит обработка элемента, потом рекурсивное углубление.
Листинг файла «bratko-3.pl».
Нет предиката noattack, который проверяет возможность добавить нового ферзя. Вместо него есть четыре списка для X, Y, восходящих диагоналей U, нисходящих диагоналей V. Выбирая ферзя, удаляются связанные элементы из этих четырёх списков. Очень ловко.
Самый быстрый вариант Братко. В полтора раза быстрее первого.
Рабочая лошадка del, описана двумя предикатами.
Первый предикат удаляет элемент. Второй ― углубляется в список. Здесь хорошо видно в действии, один из аспектов Пролога: работа с шаблонами (patterns).
Пока что не получиться написать быстрый код на Прологе. Осилить хоть какой-то код. Я напрягаюсь и пишу:
Что такое предикат search_queens(N)? Как бы я искал вариант растановки N ферзей? Наверное взял бы одного ферзя и поставил бы на первую вертикаль или X. Прикинул в уме, какие клетки находятся под ударом, а какие свободны. Поставил бы следующего ферзя…
Вот и рабочая идея! Поставил ферзя ― вычислил свободные клетки, на которые можно поставить следующего ферзя:
Вертикалью я жёстко управляю. Дальше, среди свободных клеток, прологовская машина выбирает любую клетку на X-e. Мысленно ставлю туда ферзя и убираю из свободных клеток все, оказавшиеся под ударом. Получаю новый список свободных клеток и можно переходить к следующему иксу.
Это углубление будет происходить до тех пор, пока не закончатся все свободные клетки.
Хотя нет, мне интересно, когда X = N и [].
Чтобы прологовская машина не тратила время, шарясь во внутренностях предиката, напишу:
Для пущей скорости ещё и так:
Отсекаем случай, когда свободных клеток нет, но есть ещё ферзи, которых нужно расставить.
Сам того не понимая, я учитываю, как прологовская машина будет выполнять поиск цели. Наверное это тот случай, когда надо сказать благодарю императивным рефлексам. Перед разумом стояла цель, написать быстрый код и он, анализируя, выкручивал ответы, под эту цель.
Что ещё примечательно, прологовская программа выглядит так, как я её разбирал на части. Я вижу, что дерево решения задачи (рисунок 2) максимально совпадает с тем, как прологовская машина будет искать цели.
Если я хочу быстрого кода, нужно писать предикаты так, чтобы дерево задачи совпадало с деревом обхода целей прологовской машины!
Теперь я могу ответить на вопрос, что такое search_queens(N):
Как только до меня дошла идея про дерево обхода целей, то разум сразу же начал пользоваться отсечениями и управляемым возвратом. Прологовсая машина, наткнувшись на fail, возвращается к ближайшему непросмотренному варианту предиката any. Такое себе движение в ширь. При этом работает оснавная эвристика. PROLOG не будет углубляться в подветки с узла, на котором не смог поставить ферзя на вертикали.
Осталось разобраться с предикатом remove_attacked, который производит фильтрацию списка по критерию not_attacked.
Пролог позволяет функциональные фокусы. Предикат list_filter получает на вход not_attacked(Queen), но потом предикат call(not_attacked(Queen), Cell), превратит его в not_attacked(Queen, Cell).
Остальные предикаты не вызывают трудностей.
Листинг файла «my-1.pl».
Листинг файла «common.pl».
Как-то так получилось, что у меня не возвращается список, найденных ферзей. Вместо этого используются динамический предикат queens, с помощью которого я могу сохранять список найденных ферзей. Факты сохраняется с помощью предиката assert.
Я это делаю из чистого любопытсва, ожидая, что Пролог будет медленным. Дополнительно, у меня появится точка отсчёта, позволяющая ориентироваться в результатах опытов.
Можно было бы взять Си, но =) это скучно и императивно, а тут функциональный язык программирования, который (кстати) тоже, как и Пролог, вышел из кузницы INRIA.
Всеми любимый паскалевский вариант, в исполнении OCaml-а. Листинг «ocaml-1.ml».
Сижу, красными глазами смотрю на паскалевский код ― пытаюсь переписать для «верблюда» и это после Пролога. Но тут в голове что-то счёлкнуло ― код написан за минуту. Неужели тренировка разума даёт результаты?
Нужно сравнивать с эквивалентным кодом, или хотябы кодом, построенным на одних и тех же идеях. Заглядывая в прологовский листинг «my-1.pl», начинаю писать «ocalm-2.ml».
Быстрое прототипирование! Вот она мощь Пролога во всей красе.
Пролог помог детально проанализировать задачу о ферзях. Настолько детально, что предикаты легли в основу ocaml-овских функций, без участия сознания. Помню, я что-то набирал на клавиатуре.
У Пролога не только предикаты с побочными эффектами, сам язык сплошной побочный эффект!
Опыты проводились на AMD Sempron 2200+ (1,5 ГГц; FSB 166 МГц; 2 ГБайта; 200 МГц), под управлением Ubunt-ы 8.04.2.
Для удобства, все результаты опытов сведены в таблицу.
График наглядно показывает эффективность каждого кода.
Надо следить за своими желаниями. Хотел поиграться с ферзями на Прологе, а тут получилось такое ― ха-ха. Столько сюрпризов! И тебе тренажёр разума и тебе быстрое прототипирование. В общем, зря я думал, что «мейнстримному» программисту он не нужен. Изучать PROLOG ― выгодно. Это не просто теоритическая инвестиция в знания, это практическое усовершенствование своих способностей, как программиста.
В любом случае, надеюсь, дорогой читатель, что ты смог найти для себя какие-то крупицы знаний. Но будь бдительным: PROLOG как «красная таблетка» ― назад дороги не будет. Вместо сочного бифштекса прейдётся есть кашку =) и много думать.
Когда-то PROLOG уберёг меня от плохого влияния бейсика. Даже объектно-ориентированное проектирование не смогло вырвать меня, из цепких оков императивного мышления.
До знакомства с Прологом, я смутно понимал что класс это код, а объект это данные. Шаблоны функций или классов были неприступной крепостью. Метоклассы ― магия. От элементов функционального программирования сводило зубы.
Пролог помог поставить эти парадигмы программирования на единый фундамент. Теперь (спустя много лет), играясь с ферзями, мне стало понятно, почему у него это получилось.
Тренажёр разума.
Пытаясь одолеть ферзей, вроде пишу прологовский код, но у меня возникает ощущение, что на самом деле я делаю пометки своих размышлений. Мысли плавно застывают в предикатах. Программа чудным образом повторяет дерево анализа задачи.
Разуму удобно думать, разглядывая код Пролога. Эти предикаты, то как они связаны между собой, структуры фактов, возня с переменными ― все это помогает размышлять о задаче.
Может быть потому что француз Alain Colmerauer создал PROLOG по образу и подобию разума? Конечно, Прологу далеко до разума, но некое родство ощущается. И это хорошо заметно на комбинаторных задачах.
Разум думает ― решает комбинаторную задачу. Пролог ищет цель ― решает комбинаторную задачу.
Только у разума колоссальное превосходство в качестве и колличестве эвристик, а PROLOG: гол, как сокол. Лишь хиленькая прологовская машинка, работающая на принципах поиска в графе AND/OR.
Что у Пролога, что у разума, на комбинаторных задачах, эвристики сильно сокращают время поиска решения.
Одно дело вычислять на пальцах:
print "2+2=", 2 + 2;
Другое дело, знать ответ зарание:
print "2+2=4"
Мозг содержит безумное количество эвристик-знаний. Это помогает разуму, мгновенно решать задачи, избегая комбинаторного взрыва, против которого у него есть оружие. Cпособность обобщать новые знания, поступившие в мозг, с уже существующими эвристиками, пересматривая и уточняя их.
Наверное гении понимают это и умеют целенаправлено накачивать мозг информацией так, чтобы разум обобщал эвристики там, где гению нужно решить титаническую задачу.
Известные задачи, разум гения решает быстро. На новых задачах, в условиях жесткой нехватки информации, разум гения умудряется разглядеть решение там, где обычный, не треннированный разум, даже и не подумал бы искать.
Я не гений, тем более не был им, на заре карьеры, когда познакомился с Прологом. Однако теперь понимаю, что дал Пролог. Он дал возможность разуму, разглядеть эвристику, позволяющую эффективно анализировать задачи, производить их оптимальную декомпозицию, вплоть до написания «совершенного кода».
Вот тебе и тренажёр разума. Можно возразить, что любой язык программирования способен тренировать разум. Однака, такой потрясающий резонанс, у меня получился только с PROLOG-ом.
Задача об эн-ферзях.
Поставив SWI-Prolog, я неторопливо настроил Eclipse.
Читать описание задачи и рассматривать готовый код, не поможет разуму сформировать навыки по анализу и декомпозии задачи. О написание кода я молчу. Поэтому я буду практиковаться, предворительно сформулировав цели.
Супер цель: разум должен обобщать, полученные знания, с тем, что уже находится в моей профессиональной памяти.
Цель: написать программу, которая как можно быстрее находит все верные варианты расстановки n-ферзей. Потом сравнить её с Ocaml-овским вариантом.
NP-комбинаторная задача об эн-ферзях решается перебором в глубину с возвратом. К примеру, для 4-х ферзей существует 4! = 24 варианта растановки, из которых только две дают решение.
Рассматривая дерево задачи, я понимаю, что перебирать все перестановки нет смысла. Нужна использовать эвристику, которая осечёт ветки дерева, не содержащие решения.
Подглядываю решения.
С чистой совестью, подглядываю в книгу Ивана Братко. Мне везёт как никогда. Оказывается задача о ферзях очень популярна, в образовательных целях. У Братко есть три варианта (CLP не в счёт), которые я опишу в порядке медленности исполнения.
Исходные коды переписаны для шахматных досок произвольного размера и адаптированы для пакетных опытов.
Вариант с перестановками.
Листинг файла «bratko-1.pl».
#!/usr/bin/pl -O -G128M -q -t goal -f
:- include('common.pl').
% search_all_solutions(+N)
search_all_solutions(N) :-
range(N, L),
!,
not((
solution(L, Queens),
write_solution(Queens),
fail
)).
% solution(+L, -Queens)
solution(L, Queens) :-
permutation(L, Queens),
safe(Queens).
% safe(+Queens)
safe([]).
safe([Queen | Queens]) :-
safe(Queens),
noattack(Queen, Queens, 1).
% noattack(+Queen, +Queens, +Dx)
noattack(_Queen, [], _Dx).
noattack(Y, [Y1 | Queens], Dx) :-
abs(Y1 - Y) =\= Dx,
Dx1 is Dx + 1,
noattack(Y, Queens, Dx1).
Предикат solution лаконичен. За такую выразительную краткость, программа выполняется дольше всего. PROLOG просматривать все N! вариантов.
Код использует только Y координаты клеток.
Вкусности.
При рассмотрении кода, я обратил внимание, на интересное поведение предиката permutation. Код предиката находиться в библиотечном модуле «lists.pl».
Ожидаемое поведение предиката это получение всех перестановок входящего списка [0, 1, 2]:
?- permutation([0, 1, 2], L).
L = [0, 1, 2]
Пролог выдал первый вариант, из всех возможных.
Просим прологовскую машину, выдать все перестановки:
?- permutation([0, 1, 2], L), writeln(L), fail.
false.
[0, 1, 2]
[1, 0, 2]
[1, 2, 0]
[0, 2, 1]
[2, 0, 1]
[2, 1, 0]
Похоже, начинаю понимать отличие предиката от функции. Но для ясности, пробую задать такие вопросы:
?- permutation([0, 1, 2], [0, 2, 1]).
true
?- permutation([0, 1, 2], [0, 6, 1]).
false.
Пролог ответил как истинный программист: точно, но бесполезно.
Что интересно, предикат permutation ведет себя симметрично, относительно своих переменных.
Вариант с парами.
Листинг файла «bratko-2.pl».
#!/usr/bin/pl -O -G128M -q -t goal -f
:- include('common.pl').
% xy(?N, ?Xy)
xy(4, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3]).
xy(5, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4]).
xy(6, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5]).
xy(7, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6]).
xy(8, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6, 7/_Y7]).
xy(9, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6, 7/_Y7, 8/_Y8]).
xy(10, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6, 7/_Y7, 8/_Y8, 9/_Y9]).
xy(11, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6, 7/_Y7, 8/_Y8, 9/_Y9, 10/_Y10]).
xy(12, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6, 7/_Y7, 8/_Y8, 9/_Y9, 10/_Y10, 11/_Y11]).
xy(13, [0/_Y0, 1/_Y1, 2/_Y2, 3/_Y3, 4/_Y4, 5/_Y5, 6/_Y6, 7/_Y7, 8/_Y8, 9/_Y9, 10/_Y10, 11/_Y11, 12/_Y12]).
% search_all_solutions(+N)
search_all_solutions(N) :-
xy(N, XY),
range(N, Ys),
!,
not((
solution(Ys, XY),
write_solution(XY),
fail
)).
% solution(+L, -Queens)
solution(_Ys, []).
solution(Ys, [X/Y | Others]) :-
solution(Ys, Others),
member(Y, Ys),
noattack(X/Y, Others).
% noattack(+Queen, +Queens)
noattack(_Queen, []).
noattack(X/Y, [X1/Y1 | Queens]) :-
Y =\= Y1,
abs(Y1 - Y) =\= abs(X1 - X),
noattack(X/Y, Queens).
Вариант пошустрее, уже используется поиск в глубину с возвратом.
Для обозначения клетки используется структура X/Y, где оператор / объединяет два атома. Опыт показывает, что по скорости выполнения, это выгодный способ кодирования клетки, по сравнениею с [X, Y].
Вкусности.
У предиката solution переменная Queens исходящая. Поэтому сначала происходит рекурсивное углубление, и только потом происходит вычисление элемента списка.
По другому работает со списком предикат noattack. У него переменная Queens входящая. Сначало происходит обработка элемента, потом рекурсивное углубление.
Вариант с диагоналями.
Листинг файла «bratko-3.pl».
#!/usr/bin/pl -O -G128M -q -t goal -f
:- include('common.pl').
% search_all_solutions(+N)
search_all_solutions(N) :-
A is N + 1,
range(1, A, L1),
B is -N + 1,
range(B, N, L2),
C is N * 2 + 1,
range(2, C, L3),
!,
not((
solution(L1, L2, L3, Queens),
write_solution(Queens),
fail
)).
% solution(+L1, +L2, +L3, -Queens)
solution(L1, L2, L3, Queens) :-
sol(L1, L1, L2, L3, Queens).
% sol(+Dxs, +Dy, +Du, +Dv, -Queens)
sol([], _Dy, _Du, _Dv, []).
sol([X | Dx1], Dy, Du, Dv, [Y | Queens]) :-
del(Y, Dy, Dy1),
U is X - Y,
del(U, Du, Du1),
V is X + Y,
del(V, Dv, Dv1),
sol(Dx1, Dy1, Du1, Dv1, Queens).
Нет предиката noattack, который проверяет возможность добавить нового ферзя. Вместо него есть четыре списка для X, Y, восходящих диагоналей U, нисходящих диагоналей V. Выбирая ферзя, удаляются связанные элементы из этих четырёх списков. Очень ловко.
Самый быстрый вариант Братко. В полтора раза быстрее первого.
Вкусности.
Рабочая лошадка del, описана двумя предикатами.
% del(+X, L1, -L1)
del(X, [X | L], L).
del(X, [Y | L], [Y | L1]) :-
del(X, L, L1).
Первый предикат удаляет элемент. Второй ― углубляется в список. Здесь хорошо видно в действии, один из аспектов Пролога: работа с шаблонами (patterns).
Пожиратель памяти.
Пока что не получиться написать быстрый код на Прологе. Осилить хоть какой-то код. Я напрягаюсь и пишу:
% search_all_solutions(+N)
search_all_solutions(N) :-
search_queens(N), % Найти все варианты.
report_queens_on_board. % Распечатать эти варианты.
Что такое предикат search_queens(N)? Как бы я искал вариант растановки N ферзей? Наверное взял бы одного ферзя и поставил бы на первую вертикаль или X. Прикинул в уме, какие клетки находятся под ударом, а какие свободны. Поставил бы следующего ферзя…
Вот и рабочая идея! Поставил ферзя ― вычислил свободные клетки, на которые можно поставить следующего ферзя:
% place_queen(+N, +X, +Cells, +Queens)
place_queen(N, X, Cells, Queens) :-
any(Cells, cell(X, Y)),
remove_attacked(cell(X, Y), Cells, Cells1),
X1 is X + 1,
place_queen(N, X1, Cells1, [cell(X, Y) | Queens]).
Вертикалью я жёстко управляю. Дальше, среди свободных клеток, прологовская машина выбирает любую клетку на X-e. Мысленно ставлю туда ферзя и убираю из свободных клеток все, оказавшиеся под ударом. Получаю новый список свободных клеток и можно переходить к следующему иксу.
Это углубление будет происходить до тех пор, пока не закончатся все свободные клетки.
place_queen(_N, _X, [], _Queens)
Хотя нет, мне интересно, когда X = N и [].
place_queen(N, X, [], Queens) :-
N =:= X,
!, % Куда же без отсечения.
assert(queens(Queens)).
Чтобы прологовская машина не тратила время, шарясь во внутренностях предиката, напишу:
place_queen(N, N, [], Queens) :-
!,
assert(queens(Queens)).
Для пущей скорости ещё и так:
place_queen(_N, _X, [], _Queens) :-
fail.
Отсекаем случай, когда свободных клеток нет, но есть ещё ферзи, которых нужно расставить.
Сам того не понимая, я учитываю, как прологовская машина будет выполнять поиск цели. Наверное это тот случай, когда надо сказать благодарю императивным рефлексам. Перед разумом стояла цель, написать быстрый код и он, анализируя, выкручивал ответы, под эту цель.
Что ещё примечательно, прологовская программа выглядит так, как я её разбирал на части. Я вижу, что дерево решения задачи (рисунок 2) максимально совпадает с тем, как прологовская машина будет искать цели.
Если я хочу быстрого кода, нужно писать предикаты так, чтобы дерево задачи совпадало с деревом обхода целей прологовской машины!
Теперь я могу ответить на вопрос, что такое search_queens(N):
% search_queens(+N)
search_queens(N) :-
board(N, Cells),
!,
not((
place_queen(N, 0, Cells, []),
fail
)).
Как только до меня дошла идея про дерево обхода целей, то разум сразу же начал пользоваться отсечениями и управляемым возвратом. Прологовсая машина, наткнувшись на fail, возвращается к ближайшему непросмотренному варианту предиката any. Такое себе движение в ширь. При этом работает оснавная эвристика. PROLOG не будет углубляться в подветки с узла, на котором не смог поставить ферзя на вертикали.
Осталось разобраться с предикатом remove_attacked, который производит фильтрацию списка по критерию not_attacked.
% remove_attacked(+Queen, +Cells, -Cells1).
remove_attacked(Queen, Cells, Cells1) :-
list_filter(not_attacked(Queen), Cells, Cells1).
Пролог позволяет функциональные фокусы. Предикат list_filter получает на вход not_attacked(Queen), но потом предикат call(not_attacked(Queen), Cell), превратит его в not_attacked(Queen, Cell).
% not_attacked(+Queen, +Cell)
not_attacked(cell(Qx, Qy), cell(Cx, Cy)) :-
Qy =\= Cy, % Выгодней чем с X.
Qx =\= Cx,
abs(Qx - Cx) =\= abs(Qy - Cy).
Остальные предикаты не вызывают трудностей.
Листинг файла «my-1.pl».
#!/usr/bin/pl -O -G128M -q -t goal -f
:- include('common.pl').
% cell(?X, ?Y)
:- dynamic cell/2.
% queens(?Queens)
:- dynamic queens/1.
% search_all_solutions(+N)
search_all_solutions(N) :-
search_queens(N),
report_queens_on_board.
% search_queens(+N)
search_queens(N) :-
board(N, Cells),
!,
not((
place_queen(N, 0, Cells, []),
fail
)).
% place_queen(+N, +X, +Cells, +Queens)
place_queen(N, N, [], Queens) :-
!,
assert(queens(Queens)).
place_queen(_N, _X, [], _Queens) :-
fail.
place_queen(N, X, Cells, Queens) :-
any(Cells, cell(X, Y)),
remove_attacked(cell(X, Y), Cells, Cells1),
X1 is X + 1,
place_queen(N, X1, Cells1, [cell(X, Y) | Queens]).
% remove_attacked(+Queen, +Cells, -Cells1).
remove_attacked(_, [], []).
remove_attacked(Queen, [ Cell | Cells], [Cell | Cells1]) :-
not_attacked(Queen, Cell),
!,
remove_attacked(Queen, Cells, Cells1).
remove_attacked(Queen, [ _Cell | Cells], Cells1) :-
remove_attacked(Queen, Cells, Cells1).
% not_attacked(+Queen, +Cell)
not_attacked(cell(Qx, Qy), cell(Cx, Cy)) :-
Qy =\= Cy, % Выгодней чем с X.
Qx =\= Cx,
abs(Qx - Cx) =\= abs(Qy - Cy).
% board(+N, -Cells)
board(0, []).
board(Size, Cells) :-
board_x(0, Size, Cells).
% board_x(+X, +N, -Cells)
board_x(Size, Size, []).
board_x(X, Size, Cells2) :-
board_y(X, 0, Size, Cells),
X1 is X + 1,
board_x(X1, Size, Cells1),
conc(Cells, Cells1, Cells2).
% board_x(+X, +Y, +N, -Cells)
board_y(_, Size, Size, []).
board_y(X, Y, Size, [cell(X, Y) | Cells]) :-
Y1 is Y + 1,
board_y(X, Y1, Size, Cells).
% report_queens_on_board
report_queens_on_board :-
findall(Queens, queens(Queens), L),
length(L, N),
format('Found: ~d~n', N),
report_queens_on_board(L).
% report_queens_on_board(+Queens)
report_queens_on_board([]).
report_queens_on_board([Queens | T]) :-
write_solution(Queens),
report_queens_on_board(T).
Листинг файла «common.pl».
:- use_module(library(lists)).
% goal
goal :-
read_n_from_argv(N),
search_all_solutions(N),
write_statistics,
halt
;
halt.
% goal(+N)
goal(N) :-
search_all_solutions(N),
write_statistics,
halt
;
halt.
% read_n_from_argv(-N)
read_n_from_argv(N) :-
current_prolog_flag(argv, Args),
get_argv_value(Args, '-N', SN),
atom_number(SN, N)
;
N is 4.
% get_argv_value(+Args, +Name, -Value)
get_argv_value([Arg | [Value | _Args]], Arg, Value).
get_argv_value([_NotArg | Args], Arg, Value) :-
get_argv_value(Args, Arg, Value).
% write_solution(+Term)
write_solution(Term) :-
writeln(Term).
% write_solution
write_statistics :-
statistics(runtime, [TimeMs, _]),
TimeSec is TimeMs * 0.001,
write(TimeSec),
write('\t'),
statistics(heapused, HeapUsed),
writeln(HeapUsed).
% any(+L, -X)
any([X | _], X).
any([_ | T], X) :-
any(T, X).
% conc(+L1, +L2, -L3)
conc([], L, L).
conc([X | L1], L2, [X | L3]) :-
conc(L1, L2, L3).
% del(+X, L1, -L1)
del(X, [X | L], L).
del(X, [Y | L], [Y | L1]) :-
del(X, L, L1).
% range(+N, -L)
%[0, N).
range(N, L) :-
range(0, N, L).
% range(+A, +B, -L)
% [A, B).
range(B, B, []).
range(A, B, [A | L]) :-
A1 is A + 1,
range(A1, B, L).
% Предикаты для работы со списками.
% list_iter(+Predicate, +List)
list_iter(Predicate, [H | T]) :-
call(Predicate, H),
list_iter(Predicate, T).
%
list_iter(_Predicate, []).
% list_riter(+Predicate, +List)
list_riter(Predicate, [H | T]) :-
list_riter(Predicate, T),
call(Predicate, H).
%
list_r_iter(_Predicate, []).
% list_map(+Predicate, +List, -MappedList)
list_map(Predicate, [H | T ], [MH | MT]) :-
call(Predicate, H, MH),
list_map(Predicate, T, MT).
%
list_map(_Predicate, [], []).
% list_filter(+Predicate, +List, -FilteredList)
list_filter(Predicate, [H | T ], [H | FT]) :-
call(Predicate, H),
!,
list_filter(Predicate, T, FT).
%
list_filter(Predicate, [_H | T ], FT) :-
!,
list_filter(Predicate, T, FT).
%
list_filter(_Predicate, [], []).
Вкусности.
Как-то так получилось, что у меня не возвращается список, найденных ферзей. Вместо этого используются динамический предикат queens, с помощью которого я могу сохранять список найденных ферзей. Факты сохраняется с помощью предиката assert.
PROLOG versus OCaml.
Я это делаю из чистого любопытсва, ожидая, что Пролог будет медленным. Дополнительно, у меня появится точка отсчёта, позволяющая ориентироваться в результатах опытов.
Можно было бы взять Си, но =) это скучно и императивно, а тут функциональный язык программирования, который (кстати) тоже, как и Пролог, вышел из кузницы INRIA.
Классика по верблюжьи.
Всеми любимый паскалевский вариант, в исполнении OCaml-а. Листинг «ocaml-1.ml».
exception SearchQueensDashSizeLessThenOne
let searchQueens dashSize =
if dashSize < 1 then
raise SearchQueensDashSizeLessThenOne
else
let lastIndex = dashSize - 1 in
let queens = Array.create dashSize 0 in
let canPlace x y =
let i = ref 0 in
while !i < x && y != queens.(!i) && abs (x - !i) != abs (y - queens.(!i)) do
i := !i + 1;
done;
x == !i
in
let count = ref 0 in
let rec search x =
for y = 0 to lastIndex do
if canPlace x y then (
queens.(x) <- y;
if x == lastIndex then (
for i = 0 to lastIndex do
print_int queens.(i);
print_char ' ';
done;
print_newline ();
count := !count + 1
);
search (x + 1)
);
done
in
search 0;
print_string "count: ";
print_int !count;
print_newline ()
let readArgv =
if (Array.length Sys.argv) > 1 then
int_of_string Sys.argv.(2)
else
4
let _ =
searchQueens readArgv;
print_float (Sys.time ());
print_char '\t';
print_float (Gc.allocated_bytes ());
print_newline()
Вкусности.
Сижу, красными глазами смотрю на паскалевский код ― пытаюсь переписать для «верблюда» и это после Пролога. Но тут в голове что-то счёлкнуло ― код написан за минуту. Неужели тренировка разума даёт результаты?
Прологовсие шпоры.
Нужно сравнивать с эквивалентным кодом, или хотябы кодом, построенным на одних и тех же идеях. Заглядывая в прологовский листинг «my-1.pl», начинаю писать «ocalm-2.ml».
let board size =
let rec loopY x y =
if y < size then
(x, y) :: loopY x (y + 1)
else
[]
in
let rec loopXY x =
if x < size then
(loopY x 0) @ loopXY (x + 1)
else
[]
in
loopXY 0
let print_cells cells =
List.iter
(function (x, y) ->
print_char '(';
print_int x;
print_char ',';
print_int y;
print_char ')')
cells;
print_newline ()
let searchQueens2 n =
let remove_attaced_cells (qx, qy) cells =
let not_attacked (cx, cy) =
qx != cx
&& qy != cy
&& abs(cx - qx) != abs(cy - qy)
in
List.filter not_attacked cells
in
let rec place_queen n x cells queens =
if n == x && List.length cells == 0 then
print_cells queens
else
List.iter
(fun queen ->
if (fst queen) == x then (
place_queen
n
(x + 1)
(remove_attaced_cells queen cells)
(queen :: queens)
)
)
cells
in
place_queen n 0 (board n) []
let readArgv =
if (Array.length Sys.argv) > 1 then
int_of_string Sys.argv.(2)
else
4
let _ =
searchQueens2 readArgv;
print_float (Sys.time ());
print_char '\t';
print_float (Gc.allocated_bytes ());
print_newline()
Вкусности.
Быстрое прототипирование! Вот она мощь Пролога во всей красе.
Пролог помог детально проанализировать задачу о ферзях. Настолько детально, что предикаты легли в основу ocaml-овских функций, без участия сознания. Помню, я что-то набирал на клавиатуре.
У Пролога не только предикаты с побочными эффектами, сам язык сплошной побочный эффект!
Опыты.
Опыты проводились на AMD Sempron 2200+ (1,5 ГГц; FSB 166 МГц; 2 ГБайта; 200 МГц), под управлением Ubunt-ы 8.04.2.
Для удобства, все результаты опытов сведены в таблицу.
| Код | Время исполнения, сек. | |||||
| 8 | 9 | 10 | 11 | 12 | 13 | |
| bratko-1.pl: перестановки | 0,38 ± 0,02 | 3,64 ± 0,30 | 38,33 ± 0,22 | 443,85 ± 4,32 | ||
| bratko-2.pl: пары | 0,08 ± 0,01 | 0,32 ± 0,03 | 1,67 ± 0,05 | 9,41 ± 0,31 | 55,94 ± 0,19 | 356,20 ± 2,92 |
| bratko-3.pl: диагонали | 0,08 ± 0,01 | 0,32 ± 0,01 | 1,51 ± 0,01 | 7,94 ± 0,07 | 47,17 ± 2,27 | 280,18 ± 9,55 |
| my-1.pl: пожиратель | 0,06 ± 0,01 | 0,20 ± 0,02 | 0,82 ± 0,02 | 4,02 ± 0,06 | 21,11 ± 0,25 | 118,01 ± 2,59 |
| ocaml-1.ml: классика | 0,04 ± 0,01 | 0,18 ± 0,01 | 0,86 ± 0,01 | 4,81 ± 0,04 | 29,41 ± 0,30 | 187,18 ± 1,20 |
| ocaml-1.ml: шпоры | 0,02 ± 0,01 | 0,08 ± 0,01 | 0,33 ± 0,01 | 1,61 ± 0,03 | 8,50 ± 0,04 | 47,77 ± 0,87 |
График наглядно показывает эффективность каждого кода.
Эпилог =)
Надо следить за своими желаниями. Хотел поиграться с ферзями на Прологе, а тут получилось такое ― ха-ха. Столько сюрпризов! И тебе тренажёр разума и тебе быстрое прототипирование. В общем, зря я думал, что «мейнстримному» программисту он не нужен. Изучать PROLOG ― выгодно. Это не просто теоритическая инвестиция в знания, это практическое усовершенствование своих способностей, как программиста.
В любом случае, надеюсь, дорогой читатель, что ты смог найти для себя какие-то крупицы знаний. Но будь бдительным: PROLOG как «красная таблетка» ― назад дороги не будет. Вместо сочного бифштекса прейдётся есть кашку =) и много думать.