Aleksandr SharahovНа самом деле, чтобы получить премию, этого недостаточно.

Вот тут все просто и ясно сформулировано, чтобы даже не пытались http://claymath.org/events/news/8-queens-puzzle
Поскольку язык форума - русский. А у нас в сабже даже с русским есть непонимания
(Бодаемся с зеркалами и хранением уже несколько недель) то я предлагаю перевести
публикацию и опубликовать здесь.

Никто не против? Я надеюсь моего слабого intermediate хватит чтобы осилить эти шахматные
прокламации.

Готово.

http://claymath.org/events/news/8-queens-puzzle Последняя статья о сложности n-Ферзей. Финал.

Проблема в Университете Святого Эндрюса. Университет
может указать нам на проблему тысячелетия.

Документ интересен вкладом в сложность теории, но не
решает проблему поиска решения 8-Ферзевой загадки и даже
более того N-Ферзевой.

Один из авторов, Ян Джент комментирует: "Загадка 8-Ферзей
на доске - классическая. И все решения ее давно известны.
Также известно что обобщенная загадка n-Ферзей, может
быть решена на всех досках большего размера: это загадка
размещения n ферзей на все n-по-n досках так что ферзи
не атакуют друг друга."

Новые исследования вносят сомнения что существует решение n-Ферзей,
не просто на большей доске, но также при условии что некоторые
ферзи уже размещены. Если некоторые ферзи стоят на доске nxn,
можете-ли вы найти решение n-Ферзей загадки без передвижения
вышеуказанных ферзей?

Технический вклад о котором говорит статья заключается в том что
проблема завершения n-Ферзей относится к классу NP-Полных
алгоритмов. Если это правда, то подразумевается что ЛЮБОЙ
алгоритм который может решать n-Ферзевое окончание может
быть использован опосредовано для решения любых других
проблем NP-класса.

Это неприменимо к классической оригинальной n-Ферзевой
загадке, потому-что дополнение предварительно установленных
ферзей - критически важно.

К сожалению, некоторые отчоты о нашей работы дали основание
полагать что решение 8-Ферзевой загадки, или n-ферзевой
загадки для любого n, может привести к получению награды
тысячелетия. Это не так по следующим двум причинам.

1) Как выше было сказано, документ говорит о завершении
n-Ферзевой задачи а не об оригинальной n-Ферзевой.

2) Даже нахождение алгоритмического решения загадки
n-Ферзевого Окончания для любого n, будет недостаточно.

Достаточно было-бы найти доказательство существования
полиномиального алгоритма n-Ферзей, либо доказательство
невозможности этого алгоритма.


Если вы нашли неточности в переводе - сообщайте. Поправлю.

Мысли о комбинаторике. Ферзи 4х4 имеют 4! = 24 решений из которых
большая часть - некорректны. Они не проходят checks по диагоналям.


Возникает вопрос. Можем-ли мы улучшить генератор permutations настолько, чтобы он двигался
по последовательности пермутаций длинными прыжками сразу пропуская большую последовательность
невалидных комбинаций? Примерно так-же как и мы делали в топике генерации простых
чисел.

Сам генератор permutations - тривиален. Вы можете найти его в библиотеке stl. Либо найти
любые другие имплементации. Он будет везде одинаковый.

Найдем альтернативный генератор - изменим сложность с факториальной или по Стирлингу n в степени n
хотя-бы до более простой. Ферзевые начальные установки в данном случае - просто некие фиксированные
числа в данной последовательности которые "не двигаются".

Вы не услышали моё предложение. Ещё раз обратите внимание на алгоритм генерации permutations.

Он на 99% состоит из операций циклического вращения младших элементов разрядной сетки.

Меняет ли вращение ситуацию когда 2 ферзя под боем? Открытый вопрос.