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

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

Задача о восьми ферзях — хорошо известный пример использования методов проб и ошибок и алгоритмов с возвратами. В 1850 г. эту задачу исследовал К.Ф. Гаусс, однако полностью

он ее так и не решил: для подобных задач нет аналитического решения. Огромная изнурительная работа, терпение и аккуратность в этой сфере переложены сегодня на «плечи» компьютеров.

Итак, задача. Восемь ферзей нужно расставить на шахматной доске ($8${\alltt x}$8$) так, чтобы не один ферзь при этом не был «под боем».

Вот «грубый» вариант решения:

Procedure Popytka(i:integer);

begin

выбор положения i-го ферзя;

repeat выбор очередного положения;

if безопасно then begin поставить ферзя;

 if i<8 then begin Popytka(i+1);

if неудача then убрать ферзя

end

end

until удача or мест больше нет

end; {Popytka}

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

Пусть

$x_i$ обозначает месторасположения ферзя на $i$-й вертикали,

\noindent

$a_j$ указывает, что на $j$-й горизонтали ферзя нет,

\noindent

$b_k$ указывает, что на $k$-й диагонали с правого верхнего угла в левый нижний (угол 45^o) ферзя нет,

\noindent

$с_k$ указывает, что на $k$-й диагонали с левого верхнего угла в правый нижний (угол -45^o) ферзя нет.

Учитывая то, что на диагонали с правого верхнего угла в левый нижний

постоянна сумма координат $i$ и $j$, а на диагонали с левого верхнего угла в правый нижний постоянна их разность, получим программу, дающую лишь одно решение этой задачи:

Program Ferzi;

uses InOut;

var i: integer; q: boolean;

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

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

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

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

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

var j: integer;

begin j:=0;

repeat j:=j+1; q:=FALSE;

if (a[j]and b[i+j]and c[i-j]) then begin {если безопасно, то поставить ферзя}

x[i]:=j;

a[j]:=FALSE;

b[i+j]:=FALSE;

c[i-j]:=FALSE;

if i<8 then begin

Popytka(i+1,q);

if not q then begin {убрать ферзя}

a[j]:=TRUE;

b[i+j]:=TRUE;

c[i-j]:=TRUE

end

end

else q:=TRUE

until q or (j=8)

end; {Popytka}

begin

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

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

for i:=-7 to 7 do c[i]:=true;

Popytka(1,q);

for i:=1 to 8 do WriteInt(x[i]:4);

writeln

End. {Ferzi}

На примере задачи о восьми ферзях покажим важное обобщение алгоритма проб и ошибок. Речь идет о нахождении не одного, а всех решений поставленной задачи.

Формирование «кандидатов» на правильное решение происходит образом,

гарантирующим, что ни один кандидат не встретится более, чем один раз. То есть нужно, если найдено и зафиксировано одно решение, просто переходить к другому кандидату, предлагаемому процессом систематического перебора:

Procedure Popytka(i:integer);

var k: integer;

begin

for k:= 1 to m begin

выбор k-го кандидата;

if подходит then begin его запись;

 if i<n then begin Popytka(i+1) else печать решения;

стирание записи

end

end

end; {Popytka}

Вот программа, позволяющая найти все решения задачи о восьми ферзях:

Program VseFerzi;

uses InOut;

var i: integer;

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

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

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

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

prosedure print;

var k: integer;

begin

for k:=1 to 8 do WriteInt(x[k]:4);

writeln

end;{prin}

procedure Popytka(i: integer);

var j: integer;

begin j:=0;

for j:=1 to 8 do

if (a[j]and b[i+j]and c[i-j]) then begin

x[i]:=j;

a[j]:=FALSE;

b[i+j]:=FALSE;

c[i-j]:=FALSE;

if i<8 then Popytka(i+1)

else print;

a[j]:=TRUE; b[i+j]:=TRUE; c[i-j]:=TRUE

end

end; {Popytka}

begin

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

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

for i:=-7 to 7 do c[i]:=true;

Popytka(1);

End. {VseFerzi}


 

Эта программа отыскивает 92 решения задачи. Однако принципиально различных решений в 6 раз меньше — 12(приведенная программа не учитывает симметрию):

x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8

1 5 8 6 3 7 2 4

1 6 8 3 7 4 2 5

1 7 4 6 8 2 5 3

1 7 5 8 2 4 6 3

2 4 6 8 3 1 7 5

2 5 7 1 3 8 6 4

2 5 7 4 1 8 6 3

2 6 1 7 4 8 3 5

2 6 8 3 1 4 7 5

2 7 3 6 8 5 1 4

2 7 5 8 1 4 6 3

2 8 6 1 3 5 7 4


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике