program eightqueen\(fiutput);

[поиск одного решения задачи о восьми ферзях]

таг i: integer, q: boolean;

a: array [ 1 .-. 8] oi boolean;

b: array [ 2.. 16] of boolean;

c: array [-7.. 7] of boolean;

x: array [ 1.. Щ of integer;

procedure rry(i: integer; var q: boolean);

var j: integer; begin 7.= 0;

repeat j := j+l; q :== false; if 47] Ab[i+j] Ac[i-j] then

ф] : false; b[i-\-j] false; cp-j] -. false;

if i < 8 then

Ьфл try {i+\,q);

if -1 then i

begin a[j] := true; b{i+j] := true; c[i-j] := irue

end else q :- true

until q V 0=8) end [try] ;

begin

for I := 1 to 8 do a[i] := true;

for i ;.= 2 to 16 do fe[i] := true;

for I := -7 to 7 do c[i] := true; Jry iUq);

if q thei I

for I := 1 to 8 do write {хЩ: 4); writeln

Программа 3.4. Восемь ферзей (одно решение).

Прежде чем закончить разбор задач, связанных с шахматной доской, мы воспользуемся задачей о восьми ферзя! jinn иллюстрации важного обобщения алгоритма проб и ошибок. В общих словах это обобщение заключается в том, чтобь' находить Не одно, а все рещения поставленной задачи.

К этому обобщению легко перейти. Вспомним, что множе' ство возможных путей строится по строго определенной с* стеме, так чтобы никакой путь не предлагался более одноГ

1 5 8 6 3

1 6 8 3 7

1 7 4 6 8

1 7 5 8 2

2 4 6 8 3 2 5 7 1 3 2 5 7 4 1 2 6 17 4 2 6 8 3 1 2 7 3 6 8 2 7 5 8 1

2 8 6 1 3

Это свойство алгоритма соответствует поиску по де-bV при котором каждый узел посещается только один раз. R!,o позволяет - после того как рещение найдено и должным бразом зафиксировано - просто переходить на следующий озможный путь. Общая схема такого алгоритма (3.35) .получена из (3.29):

yrocedure try(i: integer)}

var к: integer; begin

for k := 1 to m йо begin выбор к-го пути;

if приемлемо then (З.Зб)

begin запись его

if i < п then try(i+l) else rwmmb решения; стирание записи

end

Заметим, что благодаря тому, что условие окончания цикла упростилось до одной составляющей k~ т, оператор цикла с постусловием естественно заменить на оператор цикла с параметром. К удивлению, поиск всех возможных рещений описывается более простой программой, чем поиск одного решения.

Обобщенный алгоритм, который находит все 92 рещения задачи о восьми ферзях, представлен в программе 3.5. На самом деле существует только 12 принципиально различных решений; наша программа не учитывает симметрию.

1аблица 3.2. Двенадцать решений задачи о восьми ферзях

program eightqueens (output); таг i: integer;

a: array [ 1.. 8] ot boolean;

b: array [ 2.. 16] of boolean;

c: array [-7.. 7] ot boolean;

x: array [ 1.. 8] of integer; procedure print;

var k: integer; begin for /: := 1 to 8 do write(x[k]: 4);

writeln end {print} ;

procedure try(i: integer);

vat J4nt€ger;------

begin

for J :=r I to 8 do

if a[j] hb[i+j] Ac[i-J] then begin x[i] := j;

4J] :-false; b[i+j] : false; c[i-J] := false; if t < 8 then try(i+l) e\s&print;

fiue; b[i+j] true; c[i-j] := true

end [try] ; begin

for I 1 to 8 do й[] true; for i 2 to 16 do b[i] :=з true; for i := -7 to 7 do c[i] := rwe; /i (1)

Программа 3.5. Восемь ферзей (все решения). j

В табл. 3.2 приведены первые 12 решений. Число указывает частоту проверок безопасности полей. Ее среднее значение для всех 92 решений равно 161.

э. . задача об устойчивых браках

Пусть даны два непересекающихся множества Л и 5 одинаковыми кардинальными числами, равными п. НуЖЯ найти некоторое множество пар <а, 6> из п, такое, чтобы а in Л и bin В удовлетворяли некоторым ограничениям. Д' выбора таких пар существует много разных критериев; оД№ из них называется .правилом устойчивых браков .