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

Моя прога выдает первый вариант для N=32 за 1187 мс.
Комп Cel 2.0@3.0

 

locki

То есть, если я правильно читаю результаты, одно решение для 32 ферзей искали более 20ти секунд? Здесь приводится программа на ПРОЛОГе, которая (если верить описанию) находит решение для 100 ферзей за меньше чем 0.1 секунды. Надо бы проверить

 

Взял за исходную точку код отсюда, приделал упоминавшиеся выше оптимизации и развернул рекурсию. Получилось следующее:

Код (Text):

1. #include <stdio.h>
2. #include <windows.h>
3.  
4. int count = 0;
5.  
6. void queens(int N) {
7.     int arow[32], aleft[32], aright[32], aposs[32];
8.     int poss, place, val = (1<<N)-1, pos=1;
9.  
10.     arow[1]=aleft[1]=aright[1]=0;
11.     poss=aposs[1]=val>>(N/2);
12.  
13.     while(pos){
14.         if(poss){
15.             place = poss & -poss;
16.             poss &= ~place;
17.             if(pos==1 && !poss && (N & 1))count<<=1;
18.             if(pos!=N){
19.                 aposs[pos]=poss;
20.                 poss=arow[pos+1]=arow[pos]|place;
21.                 poss|=aleft[pos+1]=(aleft[pos]|place)<<1;
22.                 poss|=aright[pos+1]=(aright[pos]|place)>>1;
23.                 aposs[++pos]=poss=~(poss) & val;
24.             } else{
25.                 ++count;
26.             }
27.         }else{
28.             poss=aposs[--pos];
29.         }
30.     }
31. }
32.  
33. void main() {
34.         int N=0;
35.     printf("Enter number of queens (1..32):");
36.     scanf("%d", &N);
37.     printf("Placing %d queens...\n", N);
38.     DWORD tick=GetTickCount();
39.     queens(N);
40.     if(!(N & 1))count<<=1;
41.     printf("%d ms.\n", GetTickCount()-tick);
42.     printf("There are %d solutions.\n", count);
43.     char c;
44.     scanf("%c",&c);
45. }

Результат:
16 - 11186 мс
17 - 83360 мс

Версия 1.3 (Black_mirror)
16 - 9404 мс
17 - 64343 мс

Для чистого С++ очень даже неплохо около 25% разницы (Pentium M, 2 GHz). Не знаю, имеет ли смысл оптимировать дальше С-шный код, так как уже начинается бред компилятора. Например если убрать строчку

if(pos==1 && !poss && (N & 1))count<<=1;

то скорость вместо увеличения падает в полтора раза. Компилятор - Microsoft C++ 12.00.

 

Хватит время мерять! Сделайте уже вклад в науку!

Вычислите число расстановок N мирных ферзей для N>25.
Или число уникальных (с точностью до отражений и поворотов) расстановок N мирных ферзей для N>23.
Или число (всех и уникальных) расстановок N мирных суперферзей для N>20. Суперферзь - это смесь ферзя и коня.

Текущее положение дел в этих вопросах обрисовано тут: http://www.durangobill.com/N_Queens.html

 

RElf

Ну ты даешь! Тут для 25 ферзей считали на 260 компьютерах полгода (цитата:{6 months, about 260 machines [PII and PIV from 450 MHz to 3.4 GHz]}, а ты... Читай внимательней то, о чем говоришь...

 

Есть число всех расстановок сверхферзей для N=21!

F(10)=4 time=1 ms speed=4000 v/s
F(11)=44 time=1 ms speed=44000 v/s
F(12)=156 time=1 ms speed=156000 v/s
F(13)=1876 time=2 ms speed=938000 v/s
F(14)=5180 time=10 ms speed=518000 v/s
F(15)=32516 time=58 ms speed=560620 v/s
F(16)=202900 time=380 ms speed=533947 v/s
F(17)=1330622 time=2584 ms speed=514946 v/s
F(18)=8924976 time=18519 ms speed=481936 v/s
F(19)=64492432 time=139s speed=463101 v/s
F(20)=495864256 time=1086s speed=456403 v/s

F(21)=3977841852 time=8883 s speed=447799 v/s

Версия в архиве чуть по медленее, но зато считает и число уникальных расстановок.

 

RElf

Число всех расстановок до N=23 приведено здесь. Правда непонятен источник.

 

У меня другое число всех расстановок получилось, это нормально?

AXv1.0:
end A(21)=3984578290 (497236090) time=6576782 ms speed=605855 v/s

 

A(14)=5180 (653) time=16 ms speed=323750 v/s
A(15)=32516 (4089) time=62 ms speed=524451 v/s
A(16)=202900 (25411) time=359 ms speed=565181 v/s
A(17)=1330622 (166463) time=2438 ms speed=545784 v/s

A(18)=8924976 (1115871) time=17766 ms speed=502362 v/s [2 threads]
A(18)=8924976 (1115871) time=17750 ms speed=502815 v/s [4 threads]
A(18)=8924976 (1115871) time=17781 ms speed=501938 v/s [8 threads]

На малых значения скорость куда-то исчезает. Считал в основном с помощью 4 потоков - получается незначительно шустрее (чудеса HT?)

Интересно - сложно ли сделать программу распределенной...

 

bogrus
Это на многопроцессорной машине получилось? Если так, то возможно всё дело в том, что я в потоках делающих перебор не поставил LOCK, перед командой увеличивающей 32х-разрядный счётчик найденных решений (для каждого потока свой). Эти счётчики основной поток периодически забирает делая xchg с регистром содержащим ноль, и добавляет к 64х-разрядному счётчику. Видимо этот xchg вклинивается когда поток на другом процессоре прочитал счётчик, чтобы сделать инкремент, но еще не успел его записать. Я добавил префиксы к этой программе, а также к FX1.3. Проверь пожалуйста старую и новую версии на меньших значениях, на них баг тоже вылезает?

alpet
Скорость уходит на создание потоков. А может просто не получилось поделить на нулевой интервал времени.

Ну сам алгоритм параллелится на ура. Ну самое сложное в распределённой программе это
защита это сбоев и от фальсификации результатов со стороны злоумышленника.

 

да на двух ядрах, сейчас стало все нормально, ещё CRLF перевернуть забыл (крякозябл получается)

Код (Text):

1.         mov dword [buf],'AXv1'
2.         mov dword [buf+4],'.01:'
3.         mov dword [buf+8],$D0A

 

Black_mirror

Ну и какие получились значения? Результатами для N>20 можешь пополнить последовательность A051224 и увековечить там свое имя

 

Вот что у меня получилось для 21:
end A(21)=3977841852 (497236090) time=8621266 ms speed=461398 v/s

 

Возвращаясь к обычным ферзям: можно ускорить алгоритм еще почти в полтора раза если использовать две оси симметрии вместо одной. В аттаче соответствующая модификация С-шного кода для четных N

Результаты (Pentium M, 2 GHz):
16 - 6319 мс
18 - 321 с

Версия 1.3 (Black_mirror):
16 - 9404 ms
18 - 463 s

То есть бьет версию 1.3 больше чем на 40%. Для нечетных N принцип тот же самый, но я замучился с компилятором воевать.

Black_mirror, приделай у себя вторую ось симметрии, тогда точно никто не догонит Суть в том, что начинать нужно не с первой строки доски, а в середине. Тогда в большинстве случаев достаточно перебрать только четверть вариантов.

 

Black_mirror

Замечательно, может тогда сделать его версию для видеокарт, по методике GPGPU? Или возможностей шейдеров для этого не хватит?

 

Stiver
Не знаю сколько там осей симметрии, я решил перебирать только уникальные варианты. В архиве очень жуткий код (для понимания), написан на Си, но он имеет шансы стать новым чемпионом (после перевода на асм).

alpet
Я не знаю как организованны шейдеры, и можно ли там делать сложные циклы или рекурсию, но когда появится десятая версия, решить на них эту задачу точно можно будет

 

Black_mirror
Файл AX11.zip у меня не открывается, говорит поврежденный архив.

Вот еще интересная ссылка, где упоминается симметрия: Non-attacking Queens Problem Page

 

Black_mirror
Привет. Тут у людей назрел вопрос почему новый навороченный "КОНРОЙ" (делающий аж 4! команды за такт) проигрывает Athlon'у 64, да еще и при большей тактовой частоте:
4.__dream_____AMD_X2-3800+_3020MHz_______403Mhz-1.5-3-2-5__12266ms
5.__colfin22____E6600_Core_2_Duo_@3.25Ghz___820Mhz-5-5-5-15___12562ms
тогда как во всех остальных тестах при равных частотах наблюдается 8-20% преимущество "Конроя"... ???

 

P.S. Кстати, я тут сделал вот это: http://benchqueens.narod.ru/
Надеюсь ты не против...

 

locki
Может троттлинг?