Задача о 19 ферзях.

Тема в разделе "WASM.A&O", создана пользователем Intro, 18 мар 2010.

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Intro
    Сколько преобразований симметрии имеет шахматная доска?
    Ось четвертого порядка, четыре зеркальных плоскости...
    Центр инверсии вроде ничего нового не дает...
     
  2. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Intro
    Кста, локальные переменные в асм-функциях на пасе для возвращения результата не нужны, он лежит в EAX
     
  3. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    А товарищ Лурье тупо считал вместе с белыми ферзями: 64!/(45!*9!*10!) ~ 10e+21
    А 10e+12, точнее 788400000000 - это и есть 25000 лет :)
    Абзац! В 1975 году комбинаторику знали даже продвинутые школьники, а в 1986 уже только академики и то тупо.
    А главное задачи сокращения перебора начали решать на ЭВМ еще в 60-х годах(на бумаге думаю еще в 19-м веке) и странно, что Лурье про это не знал.
     
  4. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Ну все равно чет слишком быстро эта прога работает.
    Вот у меня в проге даже если взять девять вложенных циклов от i_-1 до 63-i то даже с пустым (!) телом это будет 5-10 минут, точно не замечал, лень ждать было. А тут полное решение за 500ms . Чет слишком крутто...
     
  5. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    persicum
    Потому что 99.9% вариантов отсекаются после расстановки четырех-пяти ферзей. Банально не остается достаточно небитых клеток.
     
  6. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    В версии нашлась ошибка, не правельно находятся координаты белых ферзей.
    Код (Text):
    1. if KolVarFr>1 then
    2.      begin
    3.        writeln(res);
    4.        Fl:=true; i1:=Kol; // здесь ищем следущию комбинацию пустых клеток
    5.        while Fl do
    6.         begin
    7.           inc(NumPust[i1]);
    8.           for i0:=i1 to Kol-1 do
    9.                 NumPust[i0+1]:=NumPust[i0]+1;
    10.           if NumPust[i1]>(KolFr-Kol+i1) then dec(i1)
    11.                                         else Fl:=false;
    12.         end;
    13.      end;
    Здесь уже правельно:
    1 2 3
    1 2 4
    ...
    1 2 10
    1 3 4...
    а так же здесь:
    Код (Text):
    1.               KolVarFr:=1;Kol:=B1-FerWhite;F:=1;
    2.               for i:=FerWhite+1 to B1 do KolVarFr:=KolVarFr*i;
    3.               for i:=1 to Kol do F:=F*i; // кол. растановок белых ферзей -
    4.               KolVarFr:=KolVarFr div F; //KolVarFr:=(B1)!/((FerWhite)!*(Kol)!)
    Теперь версия 1.31 правельно расчитывает если ферзеё меньше 19, например 8+9:
    Найдено вариантов - 3127
    Время 12.8750 сек
    Скорость 1539099 растановок/сек
    Количество провереных растановок ферзей - 19815902
    24.03.2010 г. 16:56:32
     
  7. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    persicum

    Так там не 64!/55! ( это 9 вложенных циклов), а деленное еще на 10! Т.е. в 3 миллиона раз меньше. Т.е. пустой правильный цикл пролетит за несколько миллисекунд.
     
  8. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    Вот тут эта задача с парой позиций приводится: http://klassikpoez.boom.ru/klub/urok16.htm
     
  9. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    Интересно но эту задачу можно было решить ещё в те времена, в конце 80-х, на тех ещё 8-битвых компах, типа Радио 86 РК с 8080 процем или его аналогом Партнёр 01.01.
    Код (Text):
    1.     MOV B, 8
    2.     LDA XY
    3.     RAL
    4.     RAL
    5.     RAL
    6.     MOV E, A
    7.     XRA A
    8.     ACI BM    ; СТ. АДРЕС МАССИВА BM
    9.     MOV D, A  ; DE^=Bm[XY1,i]
    10. C1: LDAX D
    11.     MOV L, B
    12.     MOV H, M1 ; СТ. АДРЕС МАССИВА M1
    13.     ORA M
    14.     INR H     ; СТ. АДРЕС МАССИВА M2
    15.     MOV M, A
    16.     MOV L, A
    17.     MOV H, KB ; СТ. АДРЕС МАССИВА KB
    18.     MOV A, M  ;
    19.     ADI C
    20.     MOV C, A
    21.     INX D
    22.     INR B
    23.     MOV A, B
    24.     CPI 9
    25.     JC C1
    Это часть кода на Интел8080, судя по всему на одну растановку ферзя Intel8080 тратил бы ок 1000 тактов и при 2 МГц это ок 2000 рас/сек это 76 мин при 9167744, ну может и больше несколько бы вышло, макс часа 2.
    А на спектруме меньше чем за 1 час управится можно, Z80 3.5-7 МГц.
     
  10. MEPOX

    MEPOX New Member

    Публикаций:
    0
    Регистрация:
    15 авг 2008
    Сообщения:
    259
    >>так что бы чёрные не били белых а белые соотвествено чёрных
    Чета я не втыкаю а "не соответственно" это как вообще будет-то?

    Кстати я так и не понял. Ты отсекал диагонали из перебора или нет? Если уберал, то объясни как.
     
  11. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    MEPOX
    Отсекать из перебора диагонали смысла нет, имеет смысл проверять что количество свободных горизонталей(или вертикалей) не менее 4(потому что 10 ферзей минимум займут блок 4 на 3), и что количество свободных вертикалей не менее 10/количество_свободных_диагоналей с округлением вверх.
     
  12. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    Вот последния редакция проги, устранены ошибки, теперь можно задавать размер поля от 3 до 16, переделал немного алгоритм, теперь битовое поле обрабатовается по 32 бита и кол. бит подсчитывается асм. функцией popcount. Правда быстродейсвие не сильно возросло, мож надо 64 битный камень или полностью функцию нати переделать на асме с SSE2.

    ЗЫ
    И ещё, там шрифт есть его надо установить что бы можно было наглядно просматривать результат в блокноте. Сам шрифт называется Shass1 (немного опечатался :)).
     
  13. spa

    spa Active Member

    Публикаций:
    0
    Регистрация:
    9 мар 2005
    Сообщения:
    2.240
    Предлагаю реализовать на CUDA и посмотреть насколько возрастет производительность. Ну или на я OpenCL но говорят куда побыстрей будет, зато опенсл, и без гпу может работать.
     
  14. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    И ещё забыл сказать, можно с консоли задавать начальные данные, через пробел N FerBlack FerWhite это соотвествено размер поля кол. черных и белых ферзей, например "Project2.exe 7 7 7".
     
  15. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    Да, метод определения кол. бит из массива вордов рулит, теперь 8х8 с 9 и 10 ферзями прогоняет за 0.25-0.28 сек. Посмотрел код, довольно оптимальный по моему.
     
  16. max7C4

    max7C4 New Member

    Публикаций:
    0
    Регистрация:
    17 мар 2008
    Сообщения:
    1.203
    осталось написать определение количества процов, распараллелить алгоритм на все и посчитать время для такой программы. хотя и сейчас на Intel c2q q6600 выдает примерно 0,12-0,2 сек (чаще 0,16 сек)
     
  17. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    Интересно посмотреть как там на больших досок.
    9х9 12 ч. 12 б. ферзей
    Найдено вариантов - 36
    Время 8.4380 сек
    Скорость 31261846 растановок/сек
    Количество провереных растановок ферзей - 263787459
    10х10 14 ч. 15 б. ферзей.
    Найдено вариантов - 17
    Время 215.8590 сек
    Скорость 5212547 растановок/сек
    Количество провереных растановок ферзей - 1125175098
    Т.е. 12х12 уже полтора часа будут выполнятся тут уж надо делать анализ симметрии доски что бы понапрасу симметричные варианты не переберать. В прочим основной переборный модуль должен быть максимально простым, именно в простоте высокая скорость.
    И ещё SSE что не помогло скорости.
     
  18. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Да мне кажется там и 100 на 100 посчитать не сильная проблема. Это по простому всякие там диагонали горизонтали отсекать можно, оптимизации делать. По хорошему так наверняка с горы всяких эвристик напридумать можно. Я где-то в древности даже целые книги про эти ферзи видел...
     
  19. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    559
    Всем доброго времени суток.
    Короче, теперь у меня новый комп с Атлон !! Х4 640
    Вот вопрос, поддерживает он инструкцию POPCNT
    Это для АМД как SSE4a
    А так, по тактам (частоте) выполняется почти одинаково с семпроном 2500.
    Короче 0.125 сек выдал с вер. 1.45, думал быстрей выполнит.
     
  20. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    это задача - вариация на тему упаковки шаров. Поэтому решается только переборным (экспоненциальным по сложности) алгоритмом.
    а прежде чем на академика наезжать теорию сложности советую посмотреть)
    Перебор можно улучшить методом ветвей и границ, но это не делает алгоритм не экспоненциальным.
    скорее всего это и имелось ввиду, просто на детском уровне