Intro Сколько преобразований симметрии имеет шахматная доска? Ось четвертого порядка, четыре зеркальных плоскости... Центр инверсии вроде ничего нового не дает...
Intro Кста, локальные переменные в асм-функциях на пасе для возвращения результата не нужны, он лежит в EAX
А товарищ Лурье тупо считал вместе с белыми ферзями: 64!/(45!*9!*10!) ~ 10e+21 А 10e+12, точнее 788400000000 - это и есть 25000 лет Абзац! В 1975 году комбинаторику знали даже продвинутые школьники, а в 1986 уже только академики и то тупо. А главное задачи сокращения перебора начали решать на ЭВМ еще в 60-х годах(на бумаге думаю еще в 19-м веке) и странно, что Лурье про это не знал.
Ну все равно чет слишком быстро эта прога работает. Вот у меня в проге даже если взять девять вложенных циклов от i_-1 до 63-i то даже с пустым (!) телом это будет 5-10 минут, точно не замечал, лень ждать было. А тут полное решение за 500ms . Чет слишком крутто...
persicum Потому что 99.9% вариантов отсекаются после расстановки четырех-пяти ферзей. Банально не остается достаточно небитых клеток.
В версии нашлась ошибка, не правельно находятся координаты белых ферзей. Код (Text): if KolVarFr>1 then begin writeln(res); Fl:=true; i1:=Kol; // здесь ищем следущию комбинацию пустых клеток while Fl do begin inc(NumPust[i1]); for i0:=i1 to Kol-1 do NumPust[i0+1]:=NumPust[i0]+1; if NumPust[i1]>(KolFr-Kol+i1) then dec(i1) else Fl:=false; end; end; Здесь уже правельно: 1 2 3 1 2 4 ... 1 2 10 1 3 4... а так же здесь: Код (Text): KolVarFr:=1;Kol:=B1-FerWhite;F:=1; for i:=FerWhite+1 to B1 do KolVarFr:=KolVarFr*i; for i:=1 to Kol do F:=F*i; // кол. растановок белых ферзей - KolVarFr:=KolVarFr div F; //KolVarFr:=(B1)!/((FerWhite)!*(Kol)!) Теперь версия 1.31 правельно расчитывает если ферзеё меньше 19, например 8+9: Найдено вариантов - 3127 Время 12.8750 сек Скорость 1539099 растановок/сек Количество провереных растановок ферзей - 19815902 24.03.2010 г. 16:56:32
persicum Так там не 64!/55! ( это 9 вложенных циклов), а деленное еще на 10! Т.е. в 3 миллиона раз меньше. Т.е. пустой правильный цикл пролетит за несколько миллисекунд.
Интересно но эту задачу можно было решить ещё в те времена, в конце 80-х, на тех ещё 8-битвых компах, типа Радио 86 РК с 8080 процем или его аналогом Партнёр 01.01. Код (Text): MOV B, 8 LDA XY RAL RAL RAL MOV E, A XRA A ACI BM ; СТ. АДРЕС МАССИВА BM MOV D, A ; DE^=Bm[XY1,i] C1: LDAX D MOV L, B MOV H, M1 ; СТ. АДРЕС МАССИВА M1 ORA M INR H ; СТ. АДРЕС МАССИВА M2 MOV M, A MOV L, A MOV H, KB ; СТ. АДРЕС МАССИВА KB MOV A, M ; ADI C MOV C, A INX D INR B MOV A, B CPI 9 JC C1 Это часть кода на Интел8080, судя по всему на одну растановку ферзя Intel8080 тратил бы ок 1000 тактов и при 2 МГц это ок 2000 рас/сек это 76 мин при 9167744, ну может и больше несколько бы вышло, макс часа 2. А на спектруме меньше чем за 1 час управится можно, Z80 3.5-7 МГц.
>>так что бы чёрные не били белых а белые соотвествено чёрных Чета я не втыкаю а "не соответственно" это как вообще будет-то? Кстати я так и не понял. Ты отсекал диагонали из перебора или нет? Если уберал, то объясни как.
MEPOX Отсекать из перебора диагонали смысла нет, имеет смысл проверять что количество свободных горизонталей(или вертикалей) не менее 4(потому что 10 ферзей минимум займут блок 4 на 3), и что количество свободных вертикалей не менее 10/количество_свободных_диагоналей с округлением вверх.
Вот последния редакция проги, устранены ошибки, теперь можно задавать размер поля от 3 до 16, переделал немного алгоритм, теперь битовое поле обрабатовается по 32 бита и кол. бит подсчитывается асм. функцией popcount. Правда быстродейсвие не сильно возросло, мож надо 64 битный камень или полностью функцию нати переделать на асме с SSE2. ЗЫ И ещё, там шрифт есть его надо установить что бы можно было наглядно просматривать результат в блокноте. Сам шрифт называется Shass1 (немного опечатался ).
Предлагаю реализовать на CUDA и посмотреть насколько возрастет производительность. Ну или на я OpenCL но говорят куда побыстрей будет, зато опенсл, и без гпу может работать.
И ещё забыл сказать, можно с консоли задавать начальные данные, через пробел N FerBlack FerWhite это соотвествено размер поля кол. черных и белых ферзей, например "Project2.exe 7 7 7".
Да, метод определения кол. бит из массива вордов рулит, теперь 8х8 с 9 и 10 ферзями прогоняет за 0.25-0.28 сек. Посмотрел код, довольно оптимальный по моему.
осталось написать определение количества процов, распараллелить алгоритм на все и посчитать время для такой программы. хотя и сейчас на Intel c2q q6600 выдает примерно 0,12-0,2 сек (чаще 0,16 сек)
Интересно посмотреть как там на больших досок. 9х9 12 ч. 12 б. ферзей Найдено вариантов - 36 Время 8.4380 сек Скорость 31261846 растановок/сек Количество провереных растановок ферзей - 263787459 10х10 14 ч. 15 б. ферзей. Найдено вариантов - 17 Время 215.8590 сек Скорость 5212547 растановок/сек Количество провереных растановок ферзей - 1125175098 Т.е. 12х12 уже полтора часа будут выполнятся тут уж надо делать анализ симметрии доски что бы понапрасу симметричные варианты не переберать. В прочим основной переборный модуль должен быть максимально простым, именно в простоте высокая скорость. И ещё SSE что не помогло скорости.
Да мне кажется там и 100 на 100 посчитать не сильная проблема. Это по простому всякие там диагонали горизонтали отсекать можно, оптимизации делать. По хорошему так наверняка с горы всяких эвристик напридумать можно. Я где-то в древности даже целые книги про эти ферзи видел...
Всем доброго времени суток. Короче, теперь у меня новый комп с Атлон !! Х4 640 Вот вопрос, поддерживает он инструкцию POPCNT Это для АМД как SSE4a А так, по тактам (частоте) выполняется почти одинаково с семпроном 2500. Короче 0.125 сек выдал с вер. 1.45, думал быстрей выполнит.
это задача - вариация на тему упаковки шаров. Поэтому решается только переборным (экспоненциальным по сложности) алгоритмом. а прежде чем на академика наезжать теорию сложности советую посмотреть) Перебор можно улучшить методом ветвей и границ, но это не делает алгоритм не экспоненциальным. скорее всего это и имелось ввиду, просто на детском уровне
