Какая формулировка правильная?
1) На доске пусто, алгоритм должен расставить N ферзей, чтобы они не угрожали друг другу, то есть найти одну любую позицию для любого N>3.
2) На доске стоит какое то кол-во ферзей k<N, не угрожающих друг другу. Нужно доставить недостающих. Найти хотя бы одну позицию для любого N>3.
3) ...[что-то другое]

Не проще в условии потребоваться разу 8 ферзей?
Помню была такая загадка в игре "7 гость".

Одну любую - давно решена "лесенкой"
Есть 2 основных варианта постановки задачи для N ферзей:
a) найти количество всех расположений N ферзей на доске NxN,
б) найти количество всех расположений N ферзей на доске NxN, при условии, что положение К из этих N ферзей уже задано.

Обзор решений тут: http://guildalfa.ru/alsha/node/35

а понятно

> Sha

а как эта задача связана с p?=np   ?
пол-интернета забито тем, что написано, что эта задача np-полная
(np-complete у англоговорящих)

Например, доказано что вариант-б задачи из [2] можно свести к другой задаче, про которую точно известно, что она NP-полная, и наоборот.
Таким образом, если удастся решить вариант-б за полиномиальное время, то будет доказано, что P=NP.

> Sha ©   (30.10.17 00:50) [5]
> Например, доказано что вариант-б задачи из [2] можно свести
> к другой задаче, про которую точно известно, что она NP-
> полная, и наоборот.
> Таким образом, если удастся решить вариант-б за полиномиальное
> время, то будет доказано, что P=NP.

а что это за задача? где вообще доказательство можно найти?

> если удастся решить вариант-б за полиномиальное время

да но по ходу это очень сложно - там по экспоненте кол-во решений растет

знамо где, в интернете

> Sha ©   (30.10.17 01:02) [8]
> знамо где, в интернете

как сформулировать запрос? я полдня интернет читал а этой задачи не встретил

> да но по ходу это очень сложно - там по экспоненте кол-во решений растет

сумма геометрической прогрессии тоже по экспоненте растет

вот это наверное?

https://jair.org/media/5512/live-5512-10126-jair.pdf

но я не силен в английском

Вот здесь разъясняют суть задачи http://claymath.org/events/news/8-queens-puzzle
и там же есть нужная тебе ссылка.

Также была ссылка у тех, кто всю кашу недавнюю заварил.

> но я не силен в английском

ну и зачем, тогда нужна ссылка? )

> http://claymath.org/events/news/8-queens-puzzle

а вот написано, что они решают задачу завершения позиции из k ферзей до N,
а не кол-во считают.

Я правильно понял?

If correct, this means that any algorithm that can solve the
> n-Queens Completion Problem can be used indirectly to solve
> any other problem in the NP class.  This does not apply to the
> original n-Queens puzzle, because the addition of pre-placed
> queens is critical.

Они хотят знать, существует ли хотя бы одно завершение,
и если существует, то сколько их. Хотят знать точно, это важно.

Т.е. вариант-б задачи из [2].

> Хотят знать точно, это важно

то есть должна быть формула (как для суммы геометрической прогрессии),
зависящая от k и N
countCompletion = f(k,N) ?

> то есть должна быть формула

Не обязательно формула, можно любой алгоритм с полиномиальной сложностью.

точнее countCompletion = f(Mk,N), Mk - матрица координат фиксированных ферзей

> Sha ©   (30.10.17 01:42) [17]

Задача на тему
https://ic.pics.livejournal.com/xayam/26173943/28530/28530_original.png