Задача о конях. Метод перебора всевозможных вариантов расстановки поиском в глубину

Цель работы

Изучение основных стратегий решения задач. Приобретение  навыков  выбора  адекватных  стратегий в зависимости от типа задач. Выбор инструмента для реализации этих стратегий.

Задание

Задача о конях: "Какое  максимальное  количество коней можно расставить на шахматной доске так, чтобы они не били друг друга".

Метод решения

Задачу расстановки коней на шахматной доске будем решать методом перебора всевозможных вариантов расстановки поиском в глубину. Пространством состояний в данном случае будет множество позиций доски, на каждой из которых может стоять или отсутствовать конь, при этом ни один конь не бьет никакого другого. Наибольшее количество коней, которых можно расставить на стандартной доске размером 8х8 составляет 32. Это решение можно получить, расставляя коней на все белые или на все черные клетки. При полном переборе поиском в глубину для большого количества коней затрачиваемое время слишком велико, чтобы протестировать программу, т.к. количество рассматриваемых вариантов резко возрастает. Поэтому, максимальное количество коней, для которых нам удалось дождаться решения, это 25.

Основой для программы послужил алгоритм из книги И. Братко «Программирование на языке ПРОЛОГ для искусственного интеллекта». Согласно этому алгоритму мы используем целочисленные списки, в которых храним координаты полей, на которых стоят кони, которые не бьют друг друга. Для формирования списка в процессе поиска в глубину мы поступаем следующим образом: в главный предикат arrange, который осуществляет обход в глубину, мы на каждом шаге передаем количество коней, оставшихся для расстановки, координаты вновь добавляемого коня и два списка, в которых хранятся координаты уже расставленных коней. При этом должны выполняться следующие правила:

1.  Кони, координаты которых перечислены в списках, не должны бить друг друга

2.  Координаты добавляемого коня должны быть в пределах доски (от 1 до 8)

3.  Добавляемый конь не должен бить ни одного коня из уже составленного списка.

При этом используется предикат notbeat, который проверяет условие 3. Он перебирает всех коней из списка и проверяет результат предиката beat, который проверяет координаты двух коней, сравнивая с теми, которые являются заведомо неправильными. Неправильные координаты определяются следующей схемой:

	В		В
В				В
		А
В				В
	В		В

Здесь буквой В показаны все позиции, которые бьет конь из позиции А. Таким образом нам нужно сравнить относительные позиции одного коня с абсолютными координатами другого, т.е. сделать 8 сравнений.

Текст программы

domains

list=integer*

predicates

belong(integer, list);

arrange(integer,list, list);

notbeat(integer, integer, list, list);

beat(integer, integer, integer, integer);

run  

clauses

run:clearwindow,

write("Enter number of knights : "),

readint(N),

arrange(N,X,Y),

write(X),

write("\n"),

write(Y).

arrange(0,[],[]).

arrange(N, [X|XS], [Y|YS]):N>0,

M=N-1,

arrange(M, XS, YS),

belong(X, [1,2,3,4,5,6,7,8]),

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

notbeat(X, Y, XS, YS).

notbeat(_,_,[],[]).

notbeat(X, Y, [A|XTAIL], [B|YTAIL]):-

X>A,

notbeat(X, Y, XTAIL, YTAIL),

not(beat(X, Y, A, B)).

notbeat(X, Y,[A|XTAIL], [B|YTAIL]):-

X=A,

Y>B,

notbeat(X, Y, XTAIL, YTAIL),

not(beat(X, Y, A, B)).

%Проверяем, бьет ли один конь другого

beat(X,Y,A,B):- A=X+1, B=Y+2.

beat(X,Y,A,B):- A=X-1, B=Y+2.

beat(X,Y,A,B):- A=X+1, B=Y-2.

beat(X,Y,A,B):- A=X-1, B=Y-2. 

beat(X,Y,A,B):- A=X+2, B=Y+1.

beat(X,Y,A,B):- A=X-2, B=Y+1.

beat(X,Y,A,B):- A=X+2, B=Y-1.

beat(X,Y,A,B):- A=X-2, B=Y-1.

belong(Y,[Y|L]).

belong(Y,[Z|L]):-belong(Y,L).

goal

run.

Граф переходов

Для случая N=2

arrange(2,X,Y)

belong(X,[…])           arrange(1,X,Y)

belong(Y,[…])           belong(X,[…])     arrange(0,X,Y)

notbeat(X,Y,[1],[1])          belong(Y,[…])

notbeat(X,Y,[1],[1])                     notbeat(X,Y,[],[])

Тесты

24 коня

[7,7,7,7,7,7,7,7,4,4,4,4,4,4,4,4,1,1,1,1,1,1,1,1]

[8,7,6,5,4,3,2,1,8,7,6,5,4,3,2,1,8,7,6,5,4,3,2,1]

9 коней

[4,1,1,1,1,1,1,1,1]

[1,8,7,6,5,4,3,2,1]