1. Варнсдорф не катит на больших досках. Там прекрасно работают склейки, причем из довольно небольшого арсенала минидосок.
Некоторым аналогом Варнсдорфа в нашем случае будет не тупой переход к следующей по порядку строке, а к самой плохой строке с минимальным количеством допустимых ячеек. Думал над этим. Скорее всего получится углубиться еще на несколько ходов, но не в разы. От экспоненты это не избавляет.

2. Насчет индексирования не понял, как его пристегнуть.
Насчет сбалансированности - по идее, она есть, если смотреть с высоты птичьего полета, а в микромире необязательно.

maytonМутная статья. Я не понимаю что такое



От перестановки ферзей местами ничего не меняется.

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

maytonЕще заметил чисто такое вероятностное (probabalistic) правило.
На большинстве досок с успешной расстановкой ферзи
стоят на расстоянии прыжка коня. Ну тоесть следующий
ферзь с большой вероятностью станет на прыжок буквой "Г".

Правда есть расстановки где ферзь стоит чуть более вытянутой
буквой.

Это так для малых размеров. На больших все чаще наблюдаются отступления от этого наблюдения.


maytonAleksandr SharahovИдея здесь, конечно, не в том, чтобы поменять пару ферзей местами, а в том, чтобы изменить их положение, не меняя занятых ими строк и столбцов, если это уменьшит столкновения по диагоналям.
Можешь привести пример как это сделать?

Например, переставить ферзей с полей [0,0] и [1,2] на поля [0,2] и [1,0].

Aleksandr Sharahov,

неточность, он переставляет только конфликтующие по диагонали, т.е. с полей [0,0] и [2,2] на поля [0,2] и [2,0].

Понятно, что между собой они продолжат конфликтовать, зато суммарное количество конфликтов на доске может уменьшиться.

maytonAleksandr SharahovAleksandr Sharahov,

неточность, он переставляет только конфликтующие по диагонали, т.е. с полей [0,0] и [2,2] на поля [0,2] и [2,0].

Понятно, что между собой они продолжат конфликтовать, зато суммарное количество конфликтов на доске может уменьшиться.
В этой статье по сути нет речи о генерации всех расстановок. Насколько я понял они генерируют
некую случайную расстановку. Типа



Потом делают несколько простых проверок и устраняют наиболее конфликтующие ферзи.
Меняют их местами и продолжают до тех пор пока не получат результат.

Возможно это полином по отношению к начальной пермутации.

Но это НЕ полином по отношению ко всем расстановкам. Ведь чтобы получить
все нам придётся неизвестное число раз (по их алгоритму) кидать кости.

И где будем хранить базу уже расчитанных пермутаций? А это на минуточку 1000 под факториалом.
Ни один амазон-сторедж не схавает.

А никто и не предлагает именно так это делать.

Он делает от, что делает. А именно, находит случайное решение при заданных начальных условиях.

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

maytonЯ думаю что яйцеголовые ботаны не такие наивные. И лям бачей так просто никому не отдадут.
Задача генерации всех решений из начальных условий - не тривиальная. И здесь "с наскока"
или "карандашом на салфетке" никто ее не сделает.

Тут нужны усилия. Причем я думаю что даже негативный результат тоже будет воспринят
положительно. Тоесть даже если не будет найдено полиномиальное решение - и будет
доказано что его нет - то это тоже серъезное продвижение в науке.

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

Правда был, вроде, чувак, который говорил что-то вроде
"дайте мне всю вашу память, и я решу". Если ничего не путаю )

maytonАрхимед вроде был.

Да, нет. Из 19 века товарищ.
При этом время у него все равно было какое-то не практичное.
Всем становится пофиг на полиномиальное решение, если коэффициенты измеряются в годах.

exp98Вот самый перспективный метод )):
tip78 надо всего-лишь найти способ сразу ставить 8 фигур на доску )) Почему? потому что он неалгоритмический. Остальные методы все алгоритмические. Это немножко шутка.

Но вот выше было про изучение свойств расстановки (буква Г и т.д. - всё что бросается в глаза). Толькоя думаю, что метод тыка тут конечно может сработать, но неплохо было бы иметь теорию(-и), описыыввающую(-ие) свойства, структуру расстановок. Знает кто ссылки? хотябы рууские перессказы?

З.ы. Лично я совершенно не заинтересован ни в коей доле того самого ляма, о к-ром только вчера и узнал здесь, не влезать же в тему с нуля. А вот хитропопые Великие Британские Учёные быстро обставят всех, лишь только усекут жемчужное зерно в, извините, "навозной куче" местного штурма.

ЗЗЫ. Вот индексация. Почему, например, чел.моск достаёт свои данные примерно константно, максимум линейно. Например м.б. потому, что использует иерархический доступ.

ЗЗЗЫ. Изучение свойств расстановок. Сколько кивков было недавно ещё в сторону нервосеток. Как только встала реальная для них задача, никто о них и не вспомнил.

Это мои 5 копеек ...

Кто сетками занимается, те не только помнят. Но пока увы. Но обещают.

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

exp98Aleksandr Sharahov зато суммарное количество конфликтов на доске может уменьшиться. Вот кстати в этом направлении кто-нить копалсяс? Просто вспомнился вообще класс меодов поиска локального оптимума, не полный перебор. За симлекс-метод один чувак даже бабки получил, вернее за его применение в экономике, что ли.

Это не чувак, а Академик.

Хотел покопаться, но тот чувак из статьи опередил )

exp98Поскольку я не в теме, и руку не поднимал: А насколько полно там он всё представил?

В явном виде алгоритм не приводит, но общего описания достаточно, чтобы самостоятельно экспериментировать.
Особенно вдохновляет на это полученная в его экспериментах статистика.