Кто может сделать быстрее? "Задача о восьми Ферзях"

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

...Так как современные процессоры очень быстры я изменил размерность доски (15х15) и количество ферзей (15) соответственно, ну получилось что то отдаленно напоминающее SuperPi...
Скачать можно сдесь: http://cp.people.overclockers.ru/cgi-bin/dl.pl?id=16270&filename=Queens.rar
Исходный КОД:

Код:

Код (Text):

1.  const N=15;
2.    type Index=1..N;
3.    Rasstanovka=array [Index] of 0..N;
4. var
5.   Form1: TForm1;
6.   X:Rasstanovka;
7.   Count:integer;
8.   time1,time2,time:integer;
9. implementation
10.  
11. {$R *.dfm}
12. function P(var X:Rasstanovka;k,y:Index):boolean;
13. var i:Index;
14. begin
15.      i:=1;
16.      while (i<k)and(y<>X[i])and(abs(k-i)<>abs(y-X[i])) do inc(i);
17.      P:=i=k
18. end;
19.  
20. procedure Backtracking(k:Index);
21. var i,y:Index;
22. begin
23.    for y:=1 to N do
24.    if P(X,k,y) then
25.    begin
26.     X[k]:=y;
27.     if k=N then
28.      begin
29.        {for i:=1 to N do write(X[i]);writeln;}
30.        inc(Count);
31.        if (count mod 10000=0) then
32.        form1.label4.Caption:='Loop: '+inttostr(Count div 10000);
33.        application.ProcessMessages;
34.      end;
35.     Backtracking(k+1);
36.    end
37. end;
38.  
39. procedure TForm1.Button1Click(Sender: TObject);
40. begin
41.    Count:=0;
42.    label2.Caption:='Total: 0 variants';
43.    label1.Caption:='Replacing '+inttostr(N)+' Queens'
44.    +'     Table '+inttostr(n)+'x'+inttostr(n);
45.    time1:=gettickcount;
46.    Backtracking(1);
47.    time2:=gettickcount;
48.    time:=time2-time1;
49.    label2.Caption:='Total: '+inttostr(Count)+' variants';
50.    form1.Panel1.Caption:='Elapsed time: '+floattostr(time /1000)+' sec';
51. end;

Кто сможет оптимизировать программу по СКОРОСТИ, на любом языке, можно
добавив МНОГОПОТОЧНОСТЬ...Результаты будут проверяться на Двух процессорной м.б. на Xeon'ах 3,2Ghz которые очень похожи на П4...

Как думаете, "СИЕ" распараллелить можно? Или еще ЧЕ?

 

Код (Text):

1.  if (count mod 10000=0) then
2.        form1.label4.Caption:='Loop: '+inttostr(Count div 10000);
3.        application.ProcessMessages;

Для того, что бы никто не подумал, что все зависло... -)

 

Смысла не вижу в оптимизации. Алгоритм оптималин. Ускорить не выйдет.
Распаролелить можно. Будет скорость в 2 раза больше.
Переписав на асм может даст прирост. Вроде есть математический способ, как отказаться от рекурсии и перейти к циклам, но что это даст.

 

Код (Text):

1. include '%fasminc%\win32ax.inc'
2.  
3. .data
4.  
5. cnt dd 0
6. title   db 'test time',0
7. msg db 'F( 0'
8. n   db ')=         0'
9. v   db '',13,'time=      0'
10. t   db ' ms',13,'continue?',0
11.  
12. .code
13.  
14. ;единичные биты в ebx - свободные горизонтали
15. ;единичные биты в esi,edi - свободные диагонали
16. ;ebp - уровень рекурсии
17. work:
18.     push eax
19.     mov eax,ebx
20.     and eax,esi
21.     and eax,edi  ;единичные биты соответствуют доступным клеткам
22.     jmp work_1
23. work_0:
24.     shl edx,cl   ;1 в клетке куда ставим ферзя
25.     xor eax,edx  ;исключаем эту клетку из списка
26.     dec ebp      
27.     jz work_draw ;если последний уровень, то найден новый вариант
28.     push ebx
29.     push esi
30.     push edi
31.  
32.     xor ebx,edx  ;помечаем что горизонталь,
33.     xor esi,edx  ;обе диагонали
34.     xor edi,edx  ;заняты
35.  
36.     stc          ;при переходе к новому ряду у нас выбывают две диагонали
37.     lea esi,[esi+esi+1] ;проходящие через крайние клетки предыдущего ряда
38.     rcr edi,1    ;и добавляются две диагонали, проходящие через крайние
39.                      ;клетки нового ряда  
40.     call work
41.     pop edi
42.     pop esi
43.     pop ebx
44.     inc ebp
45. work_1:
46.     bsf ecx,eax ;ищем свободную клетку в текущем ряду
47.     mov edx,1
48.     jnz work_0  ;переход, если нашли
49.     pop eax
50.     ret
51. work_draw:
52.     inc ebp
53.     inc [cnt] ;увеличиваем счётчик найденных вариантов
54.     bsf ecx,eax
55.     mov edx,1
56.     jnz work_0
57.     pop eax
58.     ret
59.  
60. eaxtostr:
61.     xor edx,edx
62.     mov ecx,10
63.     div ecx
64.     add dl,'0'
65.     dec edi
66.     mov [edi],dl
67.     test eax,eax
68.     jnz eaxtostr
69.     ret
70.  
71. start:
72.     mov ebp,13
73.     .l0:
74.     invoke GetTickCount
75.     push eax
76.     mov [cnt],0
77.     mov eax,ebp
78.     mov edi,n
79.     call eaxtostr
80.  
81.     mov ebx,1
82.     mov ecx,ebp
83.     shl ebx,cl
84.     dec ebx
85.     mov esi,-1
86.     mov edi,-1
87.     call work
88.  
89.     invoke GetTickCount
90.     pop edx
91.     sub eax,edx
92.     mov edi,t
93.     call eaxtostr
94.     mov eax,[cnt]
95.     mov edi,v
96.     call eaxtostr
97.     invoke MessageBox,0,msg,title,MB_YESNO
98.     inc ebp
99.     cmp eax,6
100.     jz .l0
101.     invoke ExitProcess,0
102.  
103. .end start

Что еще можно сделать:
Если первого ферзя ставить только на половину клеток первого ряда, то можно ускорить алгоритм в два раза, другая половина вариантов будет зеркальным отражением. Если число клеток нечётное и первый ферзь стоит посередине ряда, то в этом случае для второго ферзя нужно перебрать только половину клеток второго ряда.

Результаты (время в секундах):
F(13)=73712 t=0.125
F(14)=365596 t=0.734
F(15)=2279184 t=4.547
F(16)=14772512 t=30
F(17)=95815104 t=212
F(18)=666090624 t=1666

 

Black_mirror
Ну ты блин даешь. Я так не умею. Ладно буду больше тринероваться и тоже попробую закодить эту задачу.

 

Заменил рекурсию циклом, выигрышь всего 10%. Но в общем такому программному разгону любой оверклокер позавидует. Они еще порога в 10 секунд не одолели, и даже двойные ядра не спасают 8)

 

Black_mirror
Дает софверник силу, перед хардварщиком!

 

Теперь проверяется только половина вариантов.

 

Тогда сделай еще интерфейс и ввод количества ферзей от 8 до ... (у меня 255) для красоты типа того http://cp.people.overclockers.ru/cgi-bin/dl.pl?id=16315&filename=Queens.rar
И будешь создателем самого быстрого РЕШЕНИЯ проблеммы ФЕРЗЕЙ, и будут люди на Over'ах тестить (Бенчмаркить) ей процы... )

 

По просьбам трудящихся - вариант для двухядерных процов.

А также для четырёхядерного и обычный вариат.

 

Black_mirror
Супер, тока еще больше "ПАНТОВ" в интерфейс...Ну там Эбаут добавь... майл свой укажи.... ну еще че-нить поприкольней... и В заголовке формы напиши "The Queens" ASM "core quatro" final version -) ну там дата и т.д.
И будем бенчить ей, а не однопоточной SuperPi.

 

ну меня еще как автора идеии... -)

 

А вот зловещий алгоритм от ИНТЕЛА который расставляет 32 ферзя за ~30сек на P4 1500Mhz

 

Как вам это:

A description of improvements and an analysis of the algorithm behavior can be found in R. Sosic and J. Gu. Fast Search Algorithms for the N-Queens Problem. IEEE Transactions on Systems, Man, and Cybernetics. Vol. 21, 6, pp. 1572-1576, Nov/Dec, 1991.

Кратко:

-)
ЭТО
132MHz PowerPC model 604 processor
512K synchronous L2 cache
Max 192MB RAM (EDO)

 

Но это похоже нахождение одной, первой, удовлетворяющей условию, расстановки. Ну не может быть, чтобы он нашел все и так быстро... И интеловский алгоритм похоже тоже для 1-й расстановки.

 

locki
Так оно и есть в общем-то.
Кстати про SuperPI. Где можно нарыть алгоритм применяемый для рассчета числа PI, с не ограниченным (точнее ограничиваемым пользователем) кол-вом цифр? Хочется сравнить его со своим...

 

вроде вот по числу пи инфа http://www.super-computing.org/

 

В последнем архиве fx.zip программы оказались с глюком.
Глюк так и не нашел - видимо не стоит заменять рекурсию циклом.
В архиве две новых версии, версия 1.1 состоит просто из 30 вложенных циклов.
А в версии 1.2 добавлен код, который на последних 20 уровнях проверяет нет ли полностью битых горизонталей или вертикалей, в этом случае оставшихся ферзей расставить нельзя.
Время работы оптимизированной версии на АтлонеХР1700+(1466МГц):
F(15) - 1.656 c
F(16) - 11
F(17) - 73
F(18) - 525
F(19) - 4160
При N=31 время ускорение примерно в два раза, но ферзи, расставленные на верхних уровнях при этом бьют практически минимальное число клеток по диагоналям, что снижает эффективность данной проверки.

 

Black_mirror, программу можно еще немного оптимизировать, если заменить поиск младшего единичного бита таким кодом (a & -a):
mov edx,eax
neg edx
and edx,eax
и заменить xor'ы sub'ами.
На моей машине (P4-3.0) получилось такое ускорение:
F(16) - 8 секунд (old), 6,2 секунды (new)

 

на сел-д 3600Мгц (180х20) с норм. приоритетом:
v 1.1 Black_mirror
F(16)=14772512 time=9141 ms speed=1616071 v/s
v 1.2 Black_mirror
F(16)=14772512 time=7609 ms speed=1941452 v/s
v 1.2 редак Jakob
F(16)=14772512 time=6032 ms speed=2449023 v/s

Да, интерфейс, конечно, все равно, сама простота...
Просьба
1. частоту обновления уменьши до 1 раза в секунду (а то аутпут, то прогу небось сильно тормозит, судя по словам К. Касперски)
2. ну сделай ты панель, груп бох, ну для красоты интерфейса, аbout и т.д.

P.S. Интересно есть еще варианты оптимизации, но не алгоритма,
а уже кода?