N Queen с предварительно определенной королевой (-ами)

Question

Исходная проблема N-Queen заключается в размещении N Queens на доске N * N.

Однако меня допрашивал один из моих академических друзей:

Есть ли NP?доказательство полноты для задачи N Queen с заранее заданными ферзями?

Определение:

Предположение:

1. N = 8,

2. Доска уже поставила 3 ​​королевы на (0,0), (2,7), (7,4).

Вопрос:

1. Есть ли какой-нибудь полиномиальный алгоритм (ы), который бы знал, что у доски есть / нет решений (ы)?

2. Или самый быстрый алгоритм по вышеуказанному вопросу?

Приложение:

1. Явное решение не будет работать из-за предопределенногоqueen (s).

Ссылка на пример изображения

Ваша помощь будет принята с благодарностью.Большое спасибо!

Answer 1

Да.

Сложность завершения n-Queens

DOI https://doi.org/10.1613/jair.5512

Ян П. Гент

Кристофер Джефферсон

Питер Найтингейл

Аннотация

Проблема n-Queens состоит в том, чтобы разместить n шахматных королев на n на n шахматную доску, чтобы две королевы не находились в одном ряду, диагональ. Проблема завершения n-Queens - вариант, датирующийся 1850, в котором некоторые королевы уже размещены, и решатель спрашивается разместить остальное, если это возможно. Мы показываем, что n-Queens Completion NP-Complete и # P-Complete. Следствием является то, что любой неагрессивное расположение королев может быть включено как часть решение более крупной проблемы n-Queens. Введем генераторы случайные случаи для завершения n-Queens и тесно связанных Проблема заблокированных n-ферзей и исключенных диагоналей. Опишем три решатели для этих проблем, и эмпирически проанализировать твердость случайно сгенерированные экземпляры. Для заблокированных n-ферзей и исключенных Задачей диагонали мы покажем существование фазового перехода связанные с трудными случаями, как было видно в других NP-Complete проблем, но естественный генератор для n-Queens Completion не сделал генерировать последовательно сложные экземпляры. Значимость этой работы что проблема n-Queens была очень широко использована в качестве ориентира в Искусственный интеллект, но выводы по нему часто являются спорными из-за простой сложности решения проблемы. Наши результаты дать альтернативные ориентиры, которые трудно теоретически и эмпирически, но для которых методы решения предназначены для n-Queens нужно минимальное или без изменений.