Проблема расстановки n ферзей

В проблеме Расстановки N ферзей, необходимо попытаться разместить на

шахматной доске N ферзей таким образом, чтобы ни один из них не был под

ударом другого. Поэтому два ферзя не могут располагаться по одной верти-

кали, горизонтали или диагонали. Для решения задачи мы обозначим номерами

ряды клеток, расположенные по горизонтали и вертикали от 1 до N. Для ну-

мерации диагоналей мы поделим их на два типа таким образом, чтобы каждая

диагональ однозначно задавалась типом и номером, вычисленным на основе

номеров рядов по горизонтали и вертикали:

Diagonal = N * Column - Row (1 тип)

Diagonal = Row * Column - 1 (2 тип)

Если смотреть на доску из левого верхнего угла, то диагональ первого

типа напоминает символ "\", а второго типа - символ "/". Нумерация диаго-

налей второго типа на доске размером 4*4 показана на рис. 18.5.

1 2 3 4

----------------

1 1 2 3 4

----------------

2 2 3 4 5

----------------

3 3 4 5 6

----------------

4 4 5 6 7

----------------

Рис. 18.5: Доска для задачи расстановки ферзей

Для решения задачи расстановки ферзей программным путем мы должны

составить список тех вертикалей, горизонталей и диагоналей, которые явля-

ются свободными, а также тех, на которых размещаются ферзи.

Положение ферзя на доске определяется номером ряда по горизонтали и

вертикали, для чего в секцию domains вводится следующее описание queen =

q(integer,integer), указывающее на позицию ферзя. Для описания множества

позиций мы можем использовать список:

queens = queen*

Аналогичным образом необходимо ввести несколько списков для указания

вертикалей, горизонталей и диагоналей, которые не заняты ферзями. Эти

списки можно описать как:

freelist = integer*

Мы будем рассматривать шахматную доску как один объект с помощью

описания:

board = board(queens,freelist,freelist,freelist,freelist)

Списки freelist содержат свободные горизонтали, вертикали и диагона-

ли первого и второго типа соответственно. Представим две позиции на шах-

матной доске размером 4*4: (1) - пустая доска, (2) - на доске один ферзь,

расположенный в верхнем левом углу.

(1) пустая доска

board([],[1,2,3,4],[1,2,3,4],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7])

(2) доска с одним ферзем

board([q(1,1)],[2,3,4],[2,3,4],[1,2,3,5,6,7],[2,3,4,5,6,7])

Теперь задача может быть решена с помощью описания отношений между

пустой доской и доской с N ферзями. Давайте введем предикат

placeN(integer,board,board)

для которого ниже запишем два предложения. Ферзи размещаются по одному до

тех пор, пока не будут заняты все вертикали и горизонтали. Это нашло от-

ражение в первом предложении, где списки вертикалей и горизонталей пусты:

placeN(_,board(D,[],[],X,Y),board(D,[],[],D1,D2)) :- !.

placeN(N,Board1,Result):-

place_a_queen(N,Board1,Board2),

placeN(N,Board2<Result).

Во втором предложении предикат place_a_queen устанавливает связь

между позициями Board1 и Board2. (В позиции Board2 на одного ферзя боль-

ше, чем в Board1). Мы используем следующее описание предиката

place_a_queen(integer,board,board)

Ключевым вопросом при решении задачи расстановки ферзей является

описание того, как нужно ставить очередного ферзя, начиная с пустой дос-

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

зей, которые уже стоят на доске:

[q(R,C):Queens]

Среди оставшихся свободных горизонталей Rows нам нужно найти ту го-

ризонталь R, на которую мы можем поместить ферзя. В то же время горизон-

таль R должна быть удалена из списка свободных горизонталей, в результате

чего будет получен новый список свободных горизонталей NewR. Эта процеду-

ра записывается как

findandremove(R,Rows,NewR)

Соответственно мы должны найти незанятую вертикаль С. С помощью R и

С могут быть вычислены диагонали, на которых помещается ферзь. Затем мы

можем проверить, находятся ли диагонали D1 и D2 в списках незанятых диа-

гоналей.

Ниже приведено предложение, реализующее эти функции:

place_a_queen(N,board(Queens,Rows,Columns,Diag1,Diag2),

board([q(R,C):Queens],NewR,NewC,NewD1,NewD2)):-

findandremove(R,Rows,NewR),

findandreove(C,Coluns,NewC),

D1=N*C-R,findandremove(D1,Diag1,NewD1),

D2=R*C-1,findandremove(D2,Diag2,NewD2).

Далее приведен полный текст этой программы. В нем содержатся неболь-

шие дополнения для предиката nqueens, так что нам нужно всего лишь ввести

целевое утверждение наподобие следующего

nqueens(5)

для получения решения задачи (в данном случае для размещения пяти ферзей

на доске размером 5*5).

/* Program CH18EX07.PRO */

domains

queen = q(integer, integer)

queens = queen*

freelist = integer*

board = board(queens, freelist, freelist, freelist,freelist)

predicates

placeN(integer, board, board)

place_a_queen(integer, board, board)

nqueens(integer)

makelist(integer, freelist)

findandremove(integer, freelist, freelist)

clauses

nqueens(N) :-

makelist(N, L), Diagonal=N*2-1, makelist(Diagonal, LL),

placeN(N, board([], L, L, LL, LL), Final), write(Final).

placeN(_, board(D, [], [],D1,D2), board(D, [], [], D1,D2)) :- !

placeN(N, Board1, Result) :-

place_a_queen(N, Board1, Board2),

placeN(N, Board2, Result).

place_a_queen(N, board(Queens, Rows, Columns, Diag1, Diag2),

board([q(R, C)|Queens], NewR, NewC, NewD1, NewD2)) :-

Row(R| NewR),

findandremove(C, Columns, NewC),

D1 = N+C-R, findandremove(D1, Diag1, NewD1),

D2 = R+C-1, findandremove(D2, Diag2, NewD2).

findandremove(X, [X|Rest], Rest).

findandremove(X, [Y|Rest], [Y|Tail]) :-

findandremove(X, Rest,Tail).

makelist(1, [1]).

makelist(N, [N|Rest]) :-

N1 = N-1, makelist(N1, Rest).