?

Log in

No account? Create an account
головоломка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

головоломка [окт. 30, 2017|09:36 pm]
Anatoly Vorobey
[Tags|]

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

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

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

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

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

Comments:
[User Picture]From: utnapishti
2017-10-30 07:46 pm
1.
Очевидно, что невозможно поставить больше 13 слонкоролей.
Я могу поставить 12.
Остаётся решить вопрос о 13.

Edited at 2017-10-30 19:46 (UTC)
(Ответить) (Thread)
[User Picture]From: ilya_dogolazky
2017-10-30 08:01 pm
диагональки пощитал?
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2017-10-30 08:05 pm
диагоналек 15, для того, чтобы убрать две, нужен saddle-point method
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2017-10-30 08:08 pm
да ничего не нужно, углы и соседние несовместимы. Ну короче я 13 расставил. https://lichess.org/editor/2p1p2p/p7/7p/p2p4/7p/p7/7p/1p1p1p2_w_-_-

Edited at 2017-10-30 20:09 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2017-10-30 08:09 pm
я знаю, про сэдл-пойнт метод это был шутка

компутером 13 расставил?
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2017-10-30 08:12 pm
Ага, неплохо. Т.е. суть задачи "как бы их (12) потеснить".
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2017-10-30 08:16 pm
сильно подозреваю, что "суть" в вопросе "какой ранг у какой-нить материцы безумного размера"
(Ответить) (Parent) (Thread)
[User Picture]From: e2pii1
2017-11-02 08:48 am
Обе задачи решаются просто компьютерным перебором всех вариантов. На C++ не особо сложный алгоритм у меня на обычном компе перебор обеих задач за <1секунды сработал.

(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2017-11-02 08:52 am
спасибо, кэп. И как быстро она считает для доски 10000000х10000000 ?

Edited at 2017-11-02 08:53 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: e2pii1
2017-11-02 09:02 am
У вас есть универсальное решение для любой доски выдающее позиции ? Решения перебором для малых N могли бы подсказать идею и позволить её проверить.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2017-11-02 09:04 am
ну вот тут есть где-то сцылка на 13 фишек на доске 8x8, попробуйте обобщить на произвольный квадрат, может получицо, может не получицо
(Ответить) (Parent) (Thread)
[User Picture]From: e2pii1
2017-11-02 09:25 am
"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
. . . . . . . .
. . . . * . * .
* . . . . . . .
. . . . . . . .
. . . . . * . .
. . . . . . . .
. . . . . . * .
* . . * . . . .


(Ответить) (Parent) (Thread)
[User Picture]From: amigofriend
2017-10-30 08:00 pm
Ждём появления слоноконей и козлотур, то бишь конеладей.
(Ответить) (Thread)
[User Picture]From: amigofriend
2017-10-30 08:04 pm
Смешались в кучу кони люди ладьи и слонокороли
И только гордый конепешка стремится в королиферзи...
(Ответить) (Thread)
[User Picture]From: chuka_lis
2017-10-30 08:36 pm
одного.
если есть два, можно будет найти возможность для атаки))

Edited at 2017-10-30 20:37 (UTC)
(Ответить) (Thread)
[User Picture]From: ivanoff272
2017-10-30 08:41 pm
1) 11?
2) 8?
(Ответить) (Thread)
[User Picture]From: avva
2017-10-30 10:29 pm
Принимается. А доказательства?
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-10-31 07:15 pm
(2) Можно конпуктером проверить, там вариантов всего ничего, меньше миллиона. Я проверил, действительно шесть не получается.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-10-30 09:10 pm
https://lichess.org/editor/8/1B4B1/3B4/6B1/B7/8/8/1B3B2_w_-_-

Почему 6 нельзя непонятно... Про ферзей говорят до сих пор непонятно толком почему 4 нельзя.
(Ответить) (Thread)
From: (Anonymous)
2017-10-31 08:43 am
1) 14
Всего однонаправленных диагоналей 15, но в двух крайних одновременно фигуры стоять не могут
https://lichess.org/editor/b7/b6b/b6b/b6b/b6b/b6b/b6b/b7_w_-_-
(Ответить) (Thread)
[User Picture]From: avva
2017-10-31 08:47 am
Нет, они нападают друг на друга как короли.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-10-31 09:54 am
Мда, прочитал слоноконь вместо слонокороль

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

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

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

Пример с 13 уже был приведен
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-10-31 07:27 pm
Можно задаться вопросом, для каких фантастических фигур ответы на вопросы 1 и 2 совпадают.

Фигура, которая может пойти вообще на любое поле, тривиальным образом подходит (ответ 1). Фигура, которая может пойти на любое поле того цвета, на котором стоит сейчас, тоже подхит (ответ 2). Но это неинтересно, поэтому лучше ограничиться фигурами, для которых все поля доски достижимы (за несколько ходов). Еще лучше ограничиться фигурами однородными и изотропными (т.е. для которых все поля и все направления равноправны, а не такими, как пешки, которые только вперед, а бьют вообще непонятно как).
(Ответить) (Thread)
[User Picture]From: Anatoly Borodin
2017-11-20 03:28 am

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

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

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

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