Отступление: проблема N епископов

Question

Эта проблема сводит меня с ума ... Разместите N слонов на доске NxN так, чтобы все квадраты были заняты или атакованы хотя бы одним из них.

Может кто-нибудь помочь мне с алгоритмом для решения этой проблемы?

Answer 1

_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _

Answer 2

Я предполагаю, что вы запрашиваете некоторую оптимизацию, поскольку алгоритм обратного отслеживания такой, какой он есть.

Первое, на что нужно обратить внимание, это то, что вы можете разделить черно-белое - вы берете сумму B_i * W_j, где i + j = N. Вы также можете визуализировать диагонали в виде простой сетки (с ограничениями), так как это, вероятно, сделает код более компактным и, возможно, более простым для понимания. Другая оптимизация замечает, что цвет не обязательно имеет значение - результаты для некоторых черных могут использоваться для некоторых белых. Выясните, когда это произойдет, а когда нет.

Надеюсь, что это достаточно хороший импульс - должно быть достаточно для некоторых маленьких N.

Answer 3

Существует минимальное и максимальное решение этой проблемы, оно не так тривиально.

Проверьте это Епископская проблема или более подробно

Я уверен, что вы легко найдете пример в c.

Answer 4

Зачем возвращаться? Используйте небольшое количество решений, чтобы получить доказательство.

Подойдет даже жадный алгоритм: посчитайте количество квадратов, доступных для каждого квадрата. Выберите квадрат с наибольшим охватом, который не перекрывается с ранее выбранным охватом. Повторите.

Неоднозначность генерирует горизонтальные, вертикальные и боковые отклонения от центра.

N епископов достаточно, чтобы добраться до каждого квадрата ровно с одним слоном. Если вы выберете квадраты с перекрытием досягаемости, итоговое число доступных квадратов будет ниже. Хм, может быть, вам нужно количественно определить, насколько ниже для любого данного плохого квадрата. Звучит выполнимо.

Для такого огромного проблемного пространства обратное отслеживание методом перебора не кажется многообещающим.