Задача о восьми ферзях

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

Анализ задачи. Пусть

- множество искомых расстановок (конфигураций). Рассмотрим следующий подход к решению задачи. Будем искать множество конфигураций

со следующими свойствами:

.
Имеется условие, позволяющее по элементу из
определить, принадлежит ли он
.
Имеется процедура, генерирующая все элементы из
.

С помощью процедуры из пункта 3 будем генерировать по очереди все элементы из

; для элементов из

проверяем (см. пункт 2) принадлежит ли он

: в результате в силу 1 свойства будут порождены все элементы

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

-го ферзя на

-ю горизонталь. Тогда в качестве

можно взять множество конфигураций, в которых на каждой из первых

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

Программа 4. Расстановка восьми ферзей на шахматной доске.

{ Программа выдает все комбинации ферзей, которые не бьют друг друга. Алгоритм реализован на языке программирования Turbo-Pascal } program ferz; uses crt; const desksize=8; type sizeint=1..desksize; unuses=set of sizeint; combinates=array[shortint] of sizeint; var num:byte; combinate:combinates; unuse:unuses;

function attack(combinate:combinates):boolean; var i,j:byte; rightdiag,leftdiag:combinates; begin attack:=false; for i:=1 to desksize do begin leftdiag[i]:=i+combinate[i]; rightdiag[i]:=i-combinate[i]; end; for j:=1 to desksize do for i:=1 to desksize do begin if (i<>j) and ((leftdiag[i]=leftdiag[j])or(rightdiag[i]=rightdiag[j])) then begin attack:=true; exit; end; end; end;

procedure output(combinate:combinates); var i,j:byte; begin

for i:=1 to desksize do for j:=1 to desksize do begin gotoxy(i,j); if(combinate[i]=j) then write(#2) else write(' '); end; readln; end;

procedure create(num:byte; unuse:unuses; combinate:combinates); var i:byte; begin if num<=desksize then for i:=1 to desksize do begin if i in unuse then begin combinate[num]:=i; create(num+1,unuse-[i],combinate); end; end else if not attack(combinate) then output(combinate);

end;

begin textmode(c40);

clrscr; unuse:=[1..desksize]; create(1,unuse,combinate); end.

Содержание раздела

Главная сайта