tip78ассемблер это чистые биты, а они как раз эту задачу занимают чуть менее, чем полностью
сплошные 101010
mov тут вряд ли поможет, а вот например через AND можно всю строчку помечать, как занятую

На маленьких досках "битовый" алгоритм считает завершения в несколько раз быстрее обычного (примерно 4..8). Проблема с битами появляется на досках больше 32 (64), когда в языке нет типа нужной ширины. Там придется усложнять алгоритм и делать обычный цикл по строке. Возможно, имеет смысл потратить время на досуге, чтобы реализовать это и оценить преимущества.

потерял PS: но сомневаюсь, что при N>=1000 битовый алгоритм поиска завершения будет иметь заметное преимущество перед обычным.

Dima TAleksandr SharahovПроблема с битами появляется на досках больше 32 (64), когда в языке нет типа нужной ширины. Там придется усложнять алгоритм и делать обычный цикл по строке. Возможно, имеет смысл потратить время на досуге, чтобы реализовать это и оценить преимущества.
Сделай свой класс для работы с биткартой, там ничего сложного нет. Можешь мой срисовать .

Да, я и сам его рисовал мильен раз. Проблема не в классе.

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

Aleksandr Sharahov,

все *более* разреженной.

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

Dima TAleksandr SharahovОчевидно, что битовое решение выигрывает в случае малой доски потому, что вся строка представима одним числом. Как только это нарушается возникают проблемы. Допустим, сдвиг влево еще можно реализовать в цикле сложением с переносом. Но сдвиг вправо - это тормоз. И все 4-х кратное преимущество испарится. Плюс большая доска при росте становится все менее разреженной.
В алгоритм глубоко не вникал. Тебе виднее.

Что касается сдвигов, то одинаково в любую сторону: запоминаешь то что потеряется, сдвигаешь, переходишь к следующему, сдвигаешь, добавляешь то что потерялось на предыдущем сдвиге и т.д.
Если сдвиг на 1, то можно на асме вставку сделать, если не путаю там есть команды сдвига с запоминанием потерянного во флаг процессора.

Да. Это понятно.

Но сразу получается, что мы шуроповертом пробуем починить часы. Битовый алгоритм сбалансирован и хрупок. Почти все переменные хранятся в регистрах. При таких исправлениях неизбежно добавляются новые переменные и появляется работа с памятью на запись и чтение, и отличия от обычного стираются. А в обычном мы одним IFом мы проверяем столбец и 2 диагонали, зато ничего не пишем в память. Правда IFы чаще.

exp98Вопрос возник.
Во-первых, может создать отдельно продолжение темы, но уже без денег в названии? ну не будет оно таким бурным, фигли, 20 стр уже, а дельного поискать ещё надо ... а эту закрыть.


Поддерживаю. И флуд порезать можно.

exp98Напомните, пжста, по конкретным(ому) обсуждаемым в теме алгоритмам(му). В контексте завершения начальной расстановки упоминался способ типа менять местами фишки, если новая фишка конфликтует по диагонали. Так вот плииз, какие варианты "мы" рассматривали в реализации: менять поочерёдно пары или, сразу 3-4 шт или более вместе?
Заранее спасибо за услугу.


Есть 3 способа переставлять и 2 способа наполнять:
1п. Переставлять больше 2х ферзей за раз - нигде не встречал.
2п. Переставлять 2 конфликтующих не между собой, если это уменьшает общее число конфликтов - быстро сходится, но из-за ям может понадобиться больше попыток.
3п. Переставлять 2 любых, среди которых есть хотя бы один конфликтующий, если это уменьшает общее число конфликтов - медленно сходится, но реже (почти никогда) попадает в ямы.
1н. Наполняем примерно 20% или чуть больше безконфликтно, а остальное случайно - быстрее найдем первое завершение.
2н. Наполняем все случайно - выше шанс найти завершение за меньшее число попыток.

В версии "3*10^6 ферзей за 1 мин" авторы случайного алгоритма похоже использовали вариант 1н+3п. Но у них в слайдах явная ошибка, так что точно не скажу.


exp98
И ещё сразу, чтб не плодить постов. В середине ещё темы думал, можно ли получать цепочки правильных матриц, перемножением правильных же. Молчаливо предполагая, что А^2 != А* (да и в исходных рассуждениях предполагал то же). Однако в разложениях такие цепочки не редкость, например для N=7. Я смотрел их таблицу умножения. И это видно хотя бы исходя из распределения по типам разложения для базовых - их количеств слишком много, чтобы произведения не пересекались с остальными.
У этих парные произведения дают правильные матрицы:
2 147 3625 (1)(243756)
4 25 147 36 (125763)(4)
6 2637415 (126)(475)(4)
неожиданно, что 2 * 4 похожа на 1-ю с симметрией
2*4 246 1357 (124)(365)(7)
1 1357 246 (1)(235)(476)
Наверное для бОльших N такие варианты встречаются чаще. Интересно, является ли подобное особенностью лишь варианта А^2 = А* ? Предположительно нет.

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