Комбинаторные алгоритмы для программистов



             

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


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

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

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

  1. A\subset B
    .
  2. Имеется условие, позволяющее по элементу из
    B
    определить, принадлежит ли он
    A
    .
  3. Имеется процедура, генерирующая все элементы из
    B
    .

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

B
; для элементов из
B
проверяем (см. пункт 2) принадлежит ли он
A
: в результате в силу 1 свойства будут порождены все элементы
A
.

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

k
-го ферзя на
k
-ю горизонталь. Тогда в качестве
B
можно взять множество конфигураций, в которых на каждой из первых
N
горизонталей стоит ровно по одному ферзю, причем никакие два ферзя не бьют друг друга.

Программа 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.




Содержание  Назад  Вперед