Алгоритм решения загадки N Queens Domination

Я решил более общую проблему N Queens, но теперь я ищу алгоритм для решения проблемы N Queens Domination.

«На доске размером n × n найдите число доминирования, которое представляет собой минимальное количество ферзей (или других фигур), необходимое для атаки или занятия каждой клетки. Для доски 8 × 8 число доминирования ферзя равно 5». - Википедия

Я много искал и не могу найти ничего, кроме научных статей по этой проблеме, ничего хотя бы отдаленно понятного.

Моя первая мысль - просто поставить ферзя, а затем поставить следующего ферзя на место, которое может атаковать большинство других полей, и так далее. Однако, хотя это может привести к решению, я не могу найти способ гарантировать, что это решение является минимальным.

Любая помощь будет оценена, спасибо.


algorithm puzzle chess
person Michael Robinson    schedule 04.02.2012    source источник
comment
Вы хотите решить ее за ферзей или за ферзей и другие фигуры? Я полагаю, что последнее - это просто ферзи и рыцари, но его все же решить сложнее, чем в случае только ферзей.   -  person Matthew Strawbridge    schedule 05.02.2012
comment
Пометьте домашние задания как таковые для ясности тем, кто отвечает. Особенно для более тривиальных задач полезно знать, стоит ли отвечать с точки зрения учителя или коллеги. (wiki.engr.illinois.edu/display/cs242sp12/Assignment+1.1)   -  person Aria Buckles    schedule 05.02.2012
comment
Ищу решение только для королев.   -  person Michael Robinson    schedule 05.02.2012

Ответы (3)


arrow_upward
3
arrow_downward

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

person mishadoff    schedule 04.02.2012

arrow_upward
1
arrow_downward

Поскольку это вопрос домашнего задания, я не буду предлагать решение, а буду предлагать серию вопросов, которые приведут к решению. Ниже приводится ответ на вопрос: "Можете ли вы доминировать на доске с n ферзями?" Затем вы можете найти число доминирования, проверив n = 1, n = 2, ...

1) Поместив ферзя в позицию 1 *, можете ли вы затем доминировать над всеми оставшимися позициями, не достигнутыми ферзем 1, поместив (n - 1) ферзей на (n - 1) позиции, выбранные из (2,3, ...)?

2) Если нет, можете ли вы поместить ферзя на позицию 2, а затем доминировать над всеми оставшимися позициями, не достигнутыми ферзем 1, разместив (n - 1) ферзей на (n - 1) позициях, выбранных из (3,4, ... )?

3) и так далее ... т.е. поместите сначала ферзя на позицию 3, затем на позицию 4 и т. Д.

Обратите внимание, что это решение является рекурсивным - при каждой рекурсии в качестве аргументов передаются «оставшиеся позиции для добавления ферзя» и «позиции, которые еще не достижимы ни для одного ферзя». Когда пусто "позиции, недоступные ни для одного ферзя", вы нашли решение.

* упорядочить все позиции доски каким-либо образом, например слева направо, сверху вниз. Так что на 64 позиции на доске 8x8 можно ссылаться только по индексу (1..64).

person gcbenison    schedule 06.02.2012

arrow_upward
0
arrow_downward

Следующее неэффективно, но оно будет работать.

Переформулируйте проблему как задачу целочисленного программирования. Каждый квадрат на доске равен 0 или 1. Для любого квадрата сумма самого себя и всех атакующих квадратов должна быть ровно 1. И вы хотите минимизировать общую сумму.

person wye.bee    schedule 04.02.2012