Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Расстановка шахматных фигур алгоритм и пример реализации на языке пролог

Лекция



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

Программа на ПРОЛОГе расставляет шахматные фигуры на шахматной доске, так чтобы не было побита поставленная фигура другими фигурами или другие фигуры не были побиты поставленной фигурой. Здесь нет математических вычислений для определения нахождения боя фигурами. Используются только факты и работа с ними. Другими словами программа “видит” шахматное поле подобно человеку. Программа сделана была мною за 5 часов, включая разработку алгоритма и интерфейса на Visual Prolog 5. Из-за того что вместо вычисления положения идет перебор фактов, скорость работы программы очень низкая -–секунд 30 на процессоре с 800МГц. Однако это гораздо быстрее чем “думает” человек!

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

Алгоритм решения этой задачи может быть представлен следующим образом:

  1. Инициализация доски: создание пустой доски 8х8 клеток и массивов для хранения расположения фигур.

  2. Размещение фигур: нахождение подходящего расположения фигур на доске. Для этого можно использовать различные алгоритмы, например, рекурсивный алгоритм перебора всех возможных вариантов расстановки фигур или эвристический алгоритм с использованием эвристических правил, которые помогают ограничивать количество вариантов.

  3. Проверка решения: проверка полученного расположения фигур на соответствие условиям задачи. Для этого необходимо проверить, что ни одна фигура не находится под боем другой фигуры своего цвета.

  4. Вывод решения: если полученное расположение фигур соответствует условиям задачи, то оно может быть выведено на экран или сохранено в файл.

Хороший алгоритм решения задачи расстановки шахматных фигур должен обеспечивать эффективное использование ресурсов и иметь высокую точность решения.

Расстановка шахматных фигур алгоритм и пример реализации на языке пролог

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(ПолеИз,Бъет,Поле),
% то фигура под боем
               !. Об этом говорит сайт https://intellect.icu  .              
% удостовериться что фигура не под боем
фигуры_не_под_боем(Фигура,Поле):-
               not(фигура_под_боем(Фигура,Поле)),
               !.
% ставит одну фигуру на доску
поставить_фигуру(Фигура):-
% берет любое поле
               выбрать_поле_на_доске(Поле),
% если фигура на этом поле не будет побита
% и не побьет другую фигуру
               фигуры_не_под_боем(Фигура,Поле),
% то поставим ее на доску
               assertz(стоит(Фигура,Поле)),
               !.
% расставляет фигуры на доске
поставить_фигуры1(Фигура):-
               поставить_фигуру(Фигура),
               поставить_фигуры1(Фигура),
               !.
поставить_фигуры1(Фигура):-
% вывести вариант с расстановкой
               nl,write("вариант для ", Фигура),
               стоит(Фигура,Поле),
               write(" ",Поле),
               fail.
поставить_фигуры(Фигура):-
% начальная подготовка
% перебор всех полей
               выбрать_поле_на_доске(Поле),
% очистить знания
               retractall(_,расстановки),
% поставить первую фигуру
               assertz(стоит(Фигура,Поле)),
               поставить_фигуры1(Фигура),
               !.
/* вызов предиката рсстановки */
Goal поставить_фигуры(ферзь).
%

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

Вау!! 😲 Ты еще не читал? Это зря!

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

создано: 2014-09-23
обновлено: 2023-05-19
132523



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Представление и использование знаний

Термины: Представление и использование знаний