Версия для печати темы

Автор: luka 3.07.2008 16:39

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

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.

Автор: samec 4.07.2008 1:42

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

Автор: luka 4.07.2008 3:21

Условие задачи я добавил и с работой функции помоемй тоже разобрался
(y<>X[i]) - ферзи не стоят на одной горизонтали;
(abs(k-i)<>abs(y-X[i])) - ферзи не стоят на одной диагонали;
теперь у мене другой вопрос, где реализуется сам "отход назад"