N ферзей Опции

[Pavel_25]

Вот у меня тут вопросик есть , кто может , пусть поможет мне пожалуйста - я буду очень блогадарен ему
Вопрос такой:
Написать программу которая вычисляет количество комбинации расположить N ферзей на шахматной доске
NXN (6<=N<=13) так чтобы не одна ферзь не угражала другой. этот вопрос надо решить с помощью рекурсии и минимизировать время как можно больше. Я решил этот вопрос но время вычисления моей програмы когда N=13 превышает секунду , а мне надо добится результата за меньше чем за секунду.
Я понял что можно уменьшить на 50% количество проверяемых комбинаций и это я сделал . но этого не достаточно , мне нужно у меньшить количество ещё раз на 50% как то помощью симетрии и так далее....
кто знает решения буду очень блогадарен ему.

Сообщение отредактировано: Pavel_25 - 22.01.2006 18:15

[Гость]

Будем гадать на кофейной гуще?
Как можно помочь, если неизвестно, ЧТО именно сделано?

Можно и без всяких отражений и поворотов за секунду получить результат, а можно и с этим со всем не уложиться...

[Pavel_25]

смотри... я использовал только отражения и я хочу узнать каким образом я могу улучшить свою программу.

Сообщение отредактировано: Pavel_25 - 22.01.2006 18:22

[Гость]

Да как можно улучшать, если не знаешь, что???

Ты бы показал, что сделал, посмотрим.

[Pavel_25]

хорошо... Щас покажу.....

Program checker;
Type
arrqueen=Array[1..13] Of Byte;
diag=Array[1..25,1..2] of Boolean;
arr=Array[1..13] of Boolean;
Var fin, fout: text;
	N,I:Byte;
	Max:Longint;
	Queen:arrqueen;
	diagonal:diag;
	rowok:arr;
Procedure placequeen(Column,N:Byte; diagonal:diag; rowok:arr; Var max:Longint);
Var
I:Byte;
Begin
If column>N Then Max:=Max+1
Else
  begin
	For I:=1 To N do
	  if (rowok[I]) And (diagonal[N+I-Column,1]) And (diagonal[I+Column-1,2]) Then
		begin
		  rowok[I]:=False;
		  diagonal[N+I-Column,1]:=False; diagonal[I+Column-1,2]:=False;
		  placequeen(column+1,n,diagonal,rowok,Max);
		  rowok[I]:=True;
		  diagonal[N+I-Column,1]:=True; diagonal[I+Column-1,2]:=True;
		end;
  end;
End;
Begin
	Assign(fin, 'checker.in'); Reset(fin);
	Assign(fout, 'checker.out'); Rewrite(fout);
	Readln(fin, N);
	For I:=1 to N do rowok[I]:=True;
	For I:=1 to 2*N-1 do
	  begin
	  diagonal[I,1]:=True; diagonal[I,2]:=True;
	  end;
	Max:=0;
	pqueen(1,N,queen,diagonal,rowok,Max);
	Max:=0;
	For I:=1 To N div 2 do
		begin
		  rowok[I]:=False;
		  diagonal[N+I-1,1]:=False; diagonal[I,2]:=False;
		  placequeen(2,N,diagonal,rowok,Max);
		  rowok[I]:=True;
		  diagonal[N+I-1,1]:=True; diagonal[I,2]:=True;
		end;
	If N mod 2<>0 Then
		   begin
			 I:=N div 2+1;
			 rowok[I]:=False;
			 diagonal[N+I-1,1]:=False; diagonal[I,2]:=False;
			 For I:=1 To N div 2-1 do
			   begin
				 rowok[I]:=False;
				 diagonal[N+I-2,1]:=False; diagonal[I+1,2]:=False;
				 placequeen(3,n,diagonal,rowok,Max);
				 rowok[I]:=True;
				 diagonal[N+I-2,1]:=True; diagonal[I+1,2]:=True;
			   end;
		   end;
	Writeln(fout, 2*Max);
	Close(fout);
End.

Ответ нужно предостачить в файле.

Сообщение отредактировано: Altair - 22.01.2006 18:49

[volvo]

Я не понял, чем не устраивает тот вариант, что есть у нас в FAQ? Очень быстро работает, по крайней мере, не медленнее чем приведенный, зачем опять изобретать велосипед? Есть же готовый.