головоломка

[avva]

Отличная задачка от К. Кнопа.

Представьте себе слонокороля - фигуру-гибрид в шахматах, которая ходит и как слон (по диагонали на любое расстояние), и как король (на любую клетку рядом с собой).

1. Какое наибольшее число слонокоролей можно расставить на доске так, чтобы они не атаковали друг друга?

2. Какое наименьшее число слонокоролей можно расставить на доске так, чтобы любая пустая клетка находилась под ударом одного из них? (можно больше, чем одного)

P.S. Мне нравится этот интерфейс, чтобы расставлять фигуры на доске.

Comments

[utnapishti.livejournal.com]

1.
Очевидно, что невозможно поставить больше 13 слонкоролей.
Я могу поставить 12.
Остаётся решить вопрос о 13.

[amigofriend.livejournal.com]

Ждём появления слоноконей и козлотур, то бишь конеладей.

[xxxxx.livejournal.com]

диагональки пощитал?

[amigofriend.livejournal.com]

Смешались в кучу кони люди ладьи и слонокороли
И только гордый конепешка стремится в королиферзи...

[utnapishti.livejournal.com]

диагоналек 15, для того, чтобы убрать две, нужен saddle-point method

[xxxxx.livejournal.com]

да ничего не нужно, углы и соседние несовместимы. Ну короче я 13 расставил. https://lichess.org/editor/2p1p2p/p7/7p/p2p4/7p/p7/7p/1p1p1p2_w_-_-

[utnapishti.livejournal.com]

я знаю, про сэдл-пойнт метод это был шутка

компутером 13 расставил?

[utnapishti.livejournal.com]

Ага, неплохо. Т.е. суть задачи "как бы их (12) потеснить".

[xxxxx.livejournal.com]

сильно подозреваю, что "суть" в вопросе "какой ранг у какой-нить материцы безумного размера"

[chuka-lis.livejournal.com]

одного.
если есть два, можно будет найти возможность для атаки))

[ivanoff272.livejournal.com]

1) 11?
2) 8?

[vigourik.livejournal.com]

1) 13 https://lichess.org/editor/1b1b1b1b/8/b7/7b/b3b3/7b/b7/2b1b1b1_w_-_-
2) 7 https://lichess.org/editor/6b1/1b6/8/1b4b1/8/8/1b2b2b/8_w_-_-

[(Anonymous)]

https://lichess.org/editor/8/1B4B1/3B4/6B1/B7/8/8/1B3B2_w_-_-

Почему 6 нельзя непонятно... Про ферзей говорят до сих пор непонятно толком почему 4 нельзя.

[avva.livejournal.com]

Принимается. А доказательства?

[(Anonymous)]

1) 14
Всего однонаправленных диагоналей 15, но в двух крайних одновременно фигуры стоять не могут
https://lichess.org/editor/b7/b6b/b6b/b6b/b6b/b6b/b6b/b7_w_-_-

[avva.livejournal.com]

Нет, они нападают друг на друга как короли.

[(Anonymous)]

Мда, прочитал слоноконь вместо слонокороль

Со слонокоролем получается не больше 13 диагоналей из 15

Если занята крайняя диагональ A8, то под ударом A7-B8 и H1

Или свободны обе крайние диагонали, заняты не более остальных 13-ти

Пример с 13 уже был приведен

[(Anonymous)]

(2) Можно конпуктером проверить, там вариантов всего ничего, меньше миллиона. Я проверил, действительно шесть не получается.

[(Anonymous)]

Можно задаться вопросом, для каких фантастических фигур ответы на вопросы 1 и 2 совпадают.

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

[e2pii1.livejournal.com]

Обе задачи решаются просто компьютерным перебором всех вариантов. На C++ не особо сложный алгоритм у меня на обычном компе перебор обеих задач за <1секунды сработал.

[xxxxx.livejournal.com]

спасибо, кэп. И как быстро она считает для доски 10000000х10000000 ?

[e2pii1.livejournal.com]

У вас есть универсальное решение для любой доски выдающее позиции ? Решения перебором для малых N могли бы подсказать идею и позволить её проверить.

[xxxxx.livejournal.com]

ну вот тут есть где-то сцылка на 13 фишек на доске 8x8, попробуйте обобщить на произвольный квадрат, может получицо, может не получицо

[e2pii1.livejournal.com]

"13 фишек на доске 8x8" у меня и у самого моя программа печатает, и 7 бьющих всю доску тоже (но немного другая позиция чем в ссылке ниже получилась). Но обобщить - когда-нибудь потом, у меня на работе поинтересней задачи :-)

Хотя в 1й, судя по картинке, может нехитрое универсальное решение и есть.

n=13 1,1 4,1 6,1 8,2 1,3 5,4 8,4 1,5 8,6 1,7 3,8 5,8 7,8
. . * . * . * .
* . . . . . . .
. . . . . . . *
* . . . . . . .
. . . . * . . *
* . . . . . . .
. . . . . . . *
* . . * . * . .

n=7 1,1 4,1 7,2 5,7 1,6 6,4 7,7
. . . . . . . .
. . . . * . * .
* . . . . . . .
. . . . . . . .
. . . . . * . .
. . . . . . . .
. . . . . . * .
* . . * . . . .

Другая задача

[anatoly borodin (from livejournal.com)]

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

"На шахматной доске 8×8 надо расставить белые и чёрные фигуры без пешек (8+8) так, чтобы белые фигуры не атаковали чёрные, и наоборот, и чтобы слоны одного цвета стояли на клетках разных цветов (как и в обычных шахматах)."

Пробовал гуглить, но ничего подобного не смог найти.

Re: Другая задача

[e-rubik.livejournal.com]

А в чем проблема?
https://lichess.org/editor/4bbrq/5nkr/6n1/8/8/1N6/RKN5/QRBB4_w_-_-

Re: Другая задача

[e-rubik.livejournal.com]

На доске 5x6 тоже несложно:
https://lichess.org/editor/4bbrq/5nkr/6n1/8/8/1N6/RKN5/QRBB4_w_-_-