Несколько ферзей, чтобы каждый бил ровно двух из остальных

[gipokrat]

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

[Gagarin1968]

gipokrat в сообщении #1721262 писал(а):

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

Вы имеете в виду максимальное количество ферзей?
Минимальное количество — 3, например, так:

[gris]

Раскраска доски в данной задаче не актуальна, так что вспоминаю рисование и представляю вариант с четырьмя ферзями, которые изображены чёрными кружками (ударение на а).
$\begin{picture}(320,320) \multiput(0,0)(0,40){9}% {\line(1,0){320}} \multiput(0,0)(40,0){9}% {\line(0,1){320}} \put(20,20){\circle*{20}} \put(300,20){\circle*{20}} \put(300,300){\circle*{20}} \put(300,260){\circle*{20}} \end{picture}$

[gipokrat]

Gagarin1968 в сообщении #1721266 писал(а):

gipokrat в сообщении #1721262 писал(а):

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

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

Условие гласит: "Найдите все возможные варианты." Подсказка: их много, как колен (если не считать пустой расстановки).

[sydorov]

Можно дополнить до 9-ти ферзей и, соответственно до 6-ти вариантов расположения.

$\begin{picture}(320,320) \multiput(0,0)(0,40){9}% {\line(1,0){320}} \multiput(0,0)(40,0){9}% {\line(0,1){320}} \put(20,20){\circle*{20}} \put(60,60){\circle*{20}} \put(100,100){\circle*{20}} \put(140,140){\circle*{20}} \put(180,180){\circle*{20}} \put(220,220){\circle*{20}} \put(260,260){\circle*{20}} \put(300,300){\circle*{20}} \put(20,300){\circle*{20}} \end{picture}$

gris, украл у Вас идею и разметку

[Gagarin1968]

gipokrat в сообщении #1721283 писал(а):

Условие гласит: "Найдите все возможные варианты." Подсказка: их много, как колен

Ну, во-первых, колен всего 12, и это Вам хорошо известно.
Во-вторых, как мне кажется, задача недоформулирована. Ваше условие (из стартового поста) гласит:

gipokrat в сообщении #1721262 писал(а):

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

Скорее всего, здесь пропущено слово "максимального".
Потому что это можно сделать для трёх (меньше нельзя), четырёх, пяти и т.д. ферзей.
После нескольких проб мне удалось расставить 12 ферзей:



И я не уверен, что нельзя больше. Попробую отыскать.

[Gagarin1968]

Есть, нашёл расстановку из 13 ферзей!



И я по-прежнему не уверен, что это максимум.

[mihaild]

Вложение:

download (2).png [ 18.76 Кб | Просмотров: 0 ]

ortools нашло расстановку из 14
Оптимальность пока не доказало.

[Sender]

mihaild в сообщении #1721292 писал(а):

ortools нашло расстановку из 14

Я так понимаю, ortools сводит задачу к формату, который может переварить какой-нибудь известный решатель вроде CPLEX, GLPK и т.д. Вы какой использовали?

[realeugene]

gipokrat в сообщении #1721262 писал(а):

Найдите все возможные варианты.

С точностью до симметрий?

[mihaild]

Sender в сообщении #1721293 писал(а):

Я так понимаю, ortools сводит задачу к формату, который может переварить какой-нибудь известный решатель вроде CPLEX, GLPK и т.д.

Она обертка над разными решателями. Я брал CpModel, не знаю точно, что внутри, вроде бы что-то своё.

[EUgeneUS]

mihaild в сообщении #1721292 писал(а):

Оптимальность пока не доказало.

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

UPD: Но не доказано

[gipokrat]

realeugene в сообщении #1721296 писал(а):

gipokrat в сообщении #1721262 писал(а):

Найдите все возможные варианты.

С точностью до симметрий?

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

[Gagarin1968]

EUgeneUS в сообщении #1721316 писал(а):

Ограничение сверху - 15, при этом должны быть заняты три угла.

EUgeneUS
Можете показать такую расстановку?
У меня больше 14 не получается. Всегда остаётся по меньшей мере один ферзь, бьющий трёх сородичей.

[EUgeneUS]

Gagarin1968 в сообщении #1721323 писал(а):

Можете показать такую расстановку?

Нет, и скорее всего её не существует.

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