Задача о конях. Применение поиска в глубину

1. Условие задачи

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

2. Анализ задачи

Сформулируем преложенную задачу в терминах пространства состояний:

• Вершины пространства состояний – позиции, в которых представлено несколько (возможно, 0) коней, расположенных некотором допустимом порядке на шахматной доске (ни один из них не бьет другого).
• Вершина-преемник из данной вершины может быть получена после того, как на шахматную доску будет добавлен еще один конь, причем таким образом, чтобы он не бил ни одного из уже находящихся на доске коней.

Наиболее очевидный способ решения данной задачи – применение поиска в глубину.

3. Реализация алгоритма на прологе

Для описания шахматной доски удобнее всего использовать 2 списка с координатами шахматных вертикалей и горизонталей.

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

domains

list=integer*

predicates

solution(integer,list,list);

isfree(integer,integer,list,list);

within(integer,integer);

belong(integer,list);

zz(integer,integer,integer,integer);

out(list)

clauses

solution(0,[],[]).

solution(N,[X|XS],[Y|YS]):-N>0, N1=N-1,solution(N1,XS,YS), belong(X,[1,2,3,4,5,6,7,8]), belong(Y,[1,2,3,4,5,6,7,8]), isfree(X,Y,XS,YS).

isfree(_,_,[],[]).

isfree(X,Y,[A|XTAIL],[B|YTAIL]):- X>A,isfree(X,Y,XTAIL,YTAIL),not(zz(X,Y,A,B)).

isfree(X,Y,[A|XTAIL],[B|YTAIL]):- X=A,Y>B,isfree(X,Y,XTAIL,YTAIL),not(zz(X,Y,A,B)).

zz(X,Y,A,B):- X1=X+1, X1=A, Y1=Y+2, Y1=B.

zz(X,Y,A,B):- X2=X-1, X2=A, Y2=Y+2, Y2=B.

zz(X,Y,A,B):- X3=X+1, X3=A, Y3=Y-2, Y3=B.

zz(X,Y,A,B):- X4=X-1, X4=A, Y4=Y-2, Y4=B. 

zz(X,Y,A,B):- X5=X+2, X5=A, Y5=Y+1, Y5=B.

zz(X,Y,A,B):- X6=X-2, X6=A, Y6=Y+1, Y6=B.

zz(X,Y,A,B):- X7=X+2, X7=A, Y7=Y-1, Y7=B.

zz(X,Y,A,B):- X8=X-2, X8=A, Y8=Y-1, Y8=B.

%zz(X,Y,A,B):- X=A,Y=B.

belong(Y,[Y|L]).

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

out([X]):-write(X),write("\n").

out([X|L]):-write(X),write(" "),out(L).

goal

write("Enter number of Knights : "),

readint(N),

solution(N,X,Y),

write(X),

write("\n"),

write(Y).

4. Тестирование программы

Недостатком поиска в глубину является очень быстрый рост числа вариантов с увеличением размера доски. С помощью приведенной программы удалось определить максимальное число коней, которых можно расставить на доске 6´6 (18 штук),  однако на больших досках число вариантов оказалось чересчур большим.

Для доски 5´5:

X:  5 5 5 4 4 3 3 3 2 2  1 1 1

Y:  5 3 1 4 2 5 3 1 4 2  5 3 1

Для доски 6´6:

X:  6 6 6 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1

Y:  6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1

В процессе тестирования программы выполнялась   трассировка   с   проверкой обхода   И-ИЛИ дерева. Анализируя работу программы, можно заключить, что она работает правильно.