Главная arrow Робототехника arrow Расстановка шахматных фигур
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Расстановка шахматных фигур Печать
Программа на ПРОЛОГе расставляет шахматные фигуры на шахматной доске, так чтобы не было побита поставленная фигура другими фигурами или другие фигуры не были побиты поставленной фигурой. Здесь нет математических вычислений для определения нахождения боя фигурами. Используются только факты и работа с ними. Другими словами программа “видит” шахматное поле подобно человеку. Программа сделана была мною за 5 часов, включая разработку алгоритма и интерфейса на Visual Prolog 5.2. Из-за того что вместо вычисления положения идет перебор фактов, скорость работы программы очень низкая -–секунд 30 на процессоре с 800МГц. Однако это гораздо быстрее чем “думает” человек!
 
Global domains
 
ФФФ = король; ферзь; слон; конь; ладья 
Угол = наискось; прямо 
Дальность = линия; рядом; конём
Бъёт = бъёт(Дальность,Угол); конём
Строка = string
Строки = Строка*
Поле = поле(Строка,Строка)
 
Global predicates
поставить_фигуры(ФФФ)
 
predicates
nondeterm правило(ФФФ,Бъёт)
разметка1(Строки)
разметка2(Строки)
 
clauses
% правила боя фигур
правило(король,бъёт(рядом,наискось)).
правило(король,бъёт(рядом,прямо)).
правило(ферзь,бъёт(линия,наискось)).
правило(ферзь,бъёт(линия,прямо)).
правило(слон,бъёт(линия,наискось)).
правило(конь,конём).
правило(ладья,бъёт(линия,прямо)).
 
% размеры доски по вертикали и по горизонтали
разметка1(["1","2","3","4","5","6","7","8","9","10"]).
разметка2(["a","b","c","d","e","f","g","i","k","l"]).
 
database - расстановки
% факт -  места где стоят фигуры
стоит(ФФФ,Поле)
 
domains
Напр = влево; вправо; вверх; вниз; вниз_влево; вниз_вправо;
               вверх_влево; вверх_вправо
 
%
% служебные процедуры перебора клеток
% для "понимания" правил компьютером
% заметьте, здесь "понимание" идет такое же как и человеком
% и нет ни одной математической операции.
% все построено на фактах
%
predicates
nondeterm перебор_списка_как_фактов(Строки,Строка).
элемент_слева(Строки,Строка Элемент, Строка ЭлементСлева)
элемент_справа(Строки,Строка Элемент, Строка ЭлементСправа)
поле_слева(Поле, Поле Находим)
поле_справа(Поле, Поле Находим)
поле_сверху(Поле, Поле Находим)
поле_снизу(Поле, Поле Находим)
поле_рядом(Угол,Поле,Поле Рядом)
nondeterm поле_рядом(Угол,Напр,Поле,Поле Рядом)
поле_линия(Угол,Поле,Поле Линия)
поле_коня(Угол,Поле Из, Поле)
 
clauses
% перебирает элементы списка как факты базы ПРОЛОГа
% это позволяет включить механизм отката
перебор_списка_как_фактов([Строка|_],Строка).
перебор_списка_как_фактов([_|Строки],Строка):-
               перебор_списка_как_фактов(Строки,Строка).
 
% найдет элемент слева от данного в списке
элемент_слева([ЭлементСлева,Элемент|_],Элемент,ЭлементСлева):-
               !.
элемент_слева([_|Список],Элемент,ЭлементСлева):-
               элемент_слева(Список,Элемент,ЭлементСлева),
               !.
% найдет элемент справа от данного в списке
элемент_справа([Элемент,ЭлементСправа|_],Элемент,ЭлементСправа):-
               !.
элемент_справа([_|Список],Элемент,ЭлементСправа):-
               элемент_справа(Список,Элемент,ЭлементСправа),
               !.
% берет поле рядом
поле_слева(поле(Число,Буква),поле(ЧислоСлева,Буква)):-
               разметка1(Числа),
               элемент_слева(Числа,Число,ЧислоСлева),
               !.
поле_справа(поле(Число,Буква),поле(ЧислоСправа,Буква)):-
               разметка1(Числа),
               элемент_справа(Числа,Число,ЧислоСправа),
               !.
поле_сверху(поле(Число,Буква),поле(Число,БукваСверху)):-
               разметка2(Буквы),
               элемент_слева(Буквы,Буква,БукваСверху),
               !.
поле_снизу(поле(Число,Буква),поле(Число,БукваСнизу)):-
               разметка2(Буквы),
               элемент_справа(Буквы,Буква,БукваСнизу),
               !.
 
% перебирает все поля рядом в соответствии с углом боя
поле_рядом(прямо,Поле,Поле1):-
               поле_слева(Поле,Поле1),!.
поле_рядом(прямо,Поле,Поле1):-
               поле_справа(Поле,Поле1),!.
поле_рядом(прямо,Поле,Поле1):-
               поле_сверху(Поле,Поле1),!.
поле_рядом(прямо,Поле,Поле1):-
               поле_снизу(Поле,Поле1),!.
% то же, но поля рядом с углом боя “наискось”
поле_рядом(наискось,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_снизу(Поле0,Поле1),!.
поле_рядом(наискось,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_снизу(Поле0,Поле1),!.
поле_рядом(наискось,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_сверху(Поле0,Поле1),!.
поле_рядом(наискось,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_сверху(Поле0,Поле1),!.
 
% перебор всех полей по линии боя
поле_рядом(прямо,влево,Поле,Поле1):-
               поле_слева(Поле,Поле1).
поле_рядом(прямо,влево,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_рядом(прямо,влево,Поле0,Поле1).
поле_рядом(прямо,вправо,Поле,Поле1):-
               поле_справа(Поле,Поле1).
поле_рядом(прямо,вправо,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_рядом(прямо,вправо,Поле0,Поле1).
поле_рядом(прямо,вверх,Поле,Поле1):-
               поле_сверху(Поле,Поле1).
поле_рядом(прямо,вверх,Поле,Поле1):-
               поле_сверху(Поле,Поле0),
               поле_рядом(прямо,вверх,Поле0,Поле1).
поле_рядом(прямо,вниз,Поле,Поле1):-
               поле_снизу(Поле,Поле1).
поле_рядом(прямо,вниз,Поле,Поле1):-
               поле_снизу(Поле,Поле0),
               поле_рядом(прямо,вниз,Поле0,Поле1).
 
% перебор всех полей по линии боя “наискось”
поле_рядом(наискось,вниз_влево,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_снизу(Поле0,Поле1).
поле_рядом(наискось,вниз_влево,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_снизу(Поле0,Поле2),
               поле_рядом(наискось,вниз_влево,Поле2,Поле1).
поле_рядом(наискось,вниз_вправо,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_снизу(Поле0,Поле1).
поле_рядом(наискось,вниз_вправо,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_снизу(Поле0,Поле2),
               поле_рядом(наискось,вниз_вправо,Поле2,Поле1).
поле_рядом(наискось,вверх_влево,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_сверху(Поле0,Поле1).
поле_рядом(наискось,вверх_влево,Поле,Поле1):-
               поле_слева(Поле,Поле0),
               поле_сверху(Поле0,Поле2),
               поле_рядом(наискось,вверх_влево,Поле2,Поле1).
поле_рядом(наискось,вверх_вправо,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_сверху(Поле0,Поле1).
поле_рядом(наискось,вверх_вправо,Поле,Поле1):-
               поле_справа(Поле,Поле0),
               поле_сверху(Поле0,Поле2),
               поле_рядом(наискось,вверх_вправо,Поле2,Поле1).
 
% если поля находятся на линии боя
поле_линия(прямо,Поле,Поле1):-
               поле_рядом(прямо,влево,Поле,Поле1),!.
поле_линия(прямо,Поле,Поле1):-
               поле_рядом(прямо,вправо,Поле,Поле1),!.
поле_линия(прямо,Поле,Поле1):-
               поле_рядом(прямо,вниз,Поле,Поле1),!.
поле_линия(прямо,Поле,Поле1):-
               поле_рядом(прямо,вверх,Поле,Поле1),!.
поле_линия(наискось,Поле,Поле1):-
               поле_рядом(наискось,вверх_вправо,Поле,Поле1),!.
поле_линия(наискось,Поле,Поле1):-
               поле_рядом(наискось,вверх_влево,Поле,Поле1),!.
поле_линия(наискось,Поле,Поле1):-
               поле_рядом(наискось,вниз_вправо,Поле,Поле1),!.
поле_линия(наискось,Поле,Поле1):-
               поле_рядом(наискось,вниз_влево,Поле,Поле1),!.
 
поле_коня(Напр,ПолеИз,Поле):-
% пропущено %
                !.
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% сам механизм выбора полей 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
predicates
фигура_под_боем2(Поле Из,Бъёт,Поле)
фигура_под_боем1(Поле Из,Бъёт,Поле)
фигура_под_боем(ФФФ,Поле)
фигуры_не_под_боем(ФФФ,Поле)
nondeterm выбрать_поле_на_доске(Поле)
поставить_фигуры1(ФФФ)
поставить_фигуру(ФФФ)
 
clauses
% берёт клетку на доске, в которую еще не ставили
% фигуру
выбрать_поле_на_доске(поле(Число,Буква)):-
               разметка1(Числа),
               разметка2(Буквы),
               перебор_списка_как_фактов(Числа,Число),
               перебор_списка_как_фактов(Буквы,Буква).
 
% определяет – стоят ли две фигуры под боем
%
% если это место уже занято
фигура_под_боем2(Поле,_,Поле):-!.
фигура_под_боем2(ПолеИз,бъёт(рядом,Напр),Поле):-
% если фигура стоит рядом и по направлению боя
               поле_рядом(Напр,ПолеИз,Поле),
               !.
фигура_под_боем2(ПолеИз,бъёт(линия,Напр),Поле):-
% если фигура стоит на линии боя
               поле_линия(Напр,ПолеИз,Поле),
               !.
фигура_под_боем2(ПолеИз,конём,Поле):-
% если фигура стоит на поле боя коня
               поле_коня(конём,ПолеИз,Поле),
               !.
 
% фигура под боем которую ставим
фигура_под_боем1(ПолеИз,Бъёт,Поле):-
               фигура_под_боем2(ПолеИз,Бъёт,Поле),
               !.
% фигура под боем, которя уже стоит
фигура_под_боем1(ПолеИз,Бъёт,Поле):-
               фигура_под_боем2(Поле,Бъёт,ПолеИз),
               !.
               
% фигура под боем
фигура_под_боем(Фигура,Поле):-
% перебор правил для фигуры
               правило(Фигура,Бъёт),
% перебор других фигур на доске
               стоит(_,ПолеИз),
% если Фигура с Правилом боя бьёт из своих координат данную клетку
% или наоборот
               фигура_под_боем1(ПолеИз,Бъёт,Поле),
% то фигура под боем
               !.              
% удостовериться что фигура не под боем
фигуры_не_под_боем(Фигура,Поле):-
               not(фигура_под_боем(Фигура,Поле)),
               !.
% ставит одну фигуру на доску
поставить_фигуру(Фигура):-
% берет любое поле
               выбрать_поле_на_доске(Поле),
% если фигура на этом поле не будет побита
% и не побьёт другую фигуру
               фигуры_не_под_боем(Фигура,Поле),
% то поставим её на доску
               assertz(стоит(Фигура,Поле)),
               !.
% расставляет фигуры на доске
поставить_фигуры1(Фигура):-
               поставить_фигуру(Фигура),
               поставить_фигуры1(Фигура),
               !.
поставить_фигуры1(Фигура):-
% вывести вариант с расстановкой
               nl,write("вариант для ", Фигура),
               стоит(Фигура,Поле),
               write(" ",Поле),
               fail.
               
поставить_фигуры(Фигура):-
% начальная подготовка
% перебор всех полей
               выбрать_поле_на_доске(Поле),
% очистить знания
               retractall(_,расстановки),
% поставить первую фигуру
               assertz(стоит(Фигура,Поле)),
               поставить_фигуры1(Фигура),
               !.
/* вызов предиката рсстановки */
Goal поставить_фигуры(ферзь).
%

Пролог выдает варианты расстановки для данной фигуры (ферзь). В данной программе не реализован поиск для коня. Разобрав поиск для других фигур – Вы сами сможете запросто его реализовать.