Sources
Delphi Russian Knowledge Base
DRKB - это самая большая и удобная в использовании база знаний по Дельфи в рунете, составленная Виталием Невзоровым

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

01.01.2007

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

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

X[1],...,X[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.

https://algolist.manual.ru