головоломка

[avva]

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

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

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

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

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

Comments

[utnapishti.livejournal.com]

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

[xxxxx.livejournal.com]

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

[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
. . . . . . . .
. . . . * . * .
* . . . . . . .
. . . . . . . .
. . . . . * . .
. . . . . . . .
. . . . . . * .
* . . * . . . .