Математика: Комбинаторика и перебор.

ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ.

Классической задачей, которая решается методом перебора с отходом назад считается задача о восьми ферзях: требуется перечислить все способы расстановки 8-ми ферзей на шахматной доске 8 на 8, при которых они не бьют друг друга. Эту задачу решил больше 200 лет тому назад великий математик Леонард Эйлер. Заметьте, что у него не было компьютера, но тем не менее он абсолютно верно нашел все 92 таких расстановки!

Очевидно, на каждой из 8 вертикалей должно стоять по ферзю. Каждую такую расстановку можно закодировать одномерным массивом

где X[i] - номер горизонтали для i-го ферзя. Поскольку никакие два ферзя не могут стоять на одной горизонтали (тогда они бьют друг друга), то все X[i] различны, т.е. образуют перестановку из чисел 1..8. Можно, конечно, перебрать все 8! таких перестановок и выбрать среди них те 92, которые нас интересуют. Hо число 8!=40320 довольно большое.

Поэтому мы воспользуемся алгоритмом перебора с отходом назад, который позволит значительно сократить перебор и даст ответ намного быстрее:

 program Queens;
   const N=8;
   type Index=1..N;
	Rasstanovka=array [Index] of 0..N;
   var X:Rasstanovka;
       Count:word;
   function P(var X:Rasstanovka;k,y:Index):boolean;
     var i:Index;
   begin
     i:=1;
     while (i<k)and(y<>X[i])and(abs(k-i)<>abs(y-X[i])) do inc(i);
     P:=i=k
   end;
   procedure Backtracking(k:Index);
     var i,y:Index;
   begin
     for y:=1 to N do
       if P(X,k,y) then
	 begin
	   X[k]:=y;
	   if k=N then
	     begin
	       for i:=1 to N do write(X[i]);writeln;inc(Count)
	     end;
	   Backtracking(k+1)
	 end
   end;
 begin
   Count:=0;
   writeln('Расстановки ',N,' ферзей:');
   Backtracking(1);
   writeln('Всего ',Count,' расстановок')
 end.

Вверх по странице, к оглавлению и навигации.