N ферзей, X по Y вопрос о решении проблемы с советом директоров

10

Мне задали следующий вопрос в сегодняшнем интервью, и я с тех пор об этом думаю. Я не смог ответить на него и не смог найти решение онлайн.

Учитывая шахматную доску с размерами X от Y и N королев, определите, можно ли расположить этих королев на доске так, чтобы они не могли атаковать друг друга.

Доска 2 x 3 с 2 ферзями имеет решение, поэтому алгоритм вернет true:

Q . .
. . Q

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

интервьюируемый
источник
Best First Search - это, безусловно, вариант, как и другие эвристики поиска
Джейсон
2
номинирован на один из худших вопросов на собеседовании за всю историю - если только программное обеспечение, над которым они работают, не основано на решениях для обратного отслеживания, в этом случае это абсолютно актуально
Стивен А. Лоу
1
Справедливости ради, интервьюер сказал, что это просто дополнительные кредитные вещи. Остальная часть интервью была довольно легальной ИМО. Мне было просто любопытно.
Интервью
Возможно, это был тест, если он проведет симуляцию с возвратом или (подумает о поиске) решения O (1), используя факты, изложенные Калебом в его ответе. Способность программировать простые вещи - это не все, что нужно в работе.
Сопель
домашние задания явно выходят за рамки здесь.
Вечер

Ответы:

16

Это (IMO) не очень интересная проблема с точки зрения программирования. Вы могли бы придумать рекурсивный алгоритм, который пробует каждое расположение, что-то вроде этого:

bool try_queens(Board board, int n)
{
    if (n == 0) {
        // no queens left to place, so we're done
        return true
    }
    // try each open position until we find one that works
    for each position on the board {
        if (is_empty(board, position) and not is_attacked(board, position)) {
            place_queen(board, position)
            if (try_queens(board, n-1)) {
                return true
            }
            remove_queen(board, position)
        }
    }
    // if we get this far, there's no available position
    return false
}

main()
{
    initialize board(X,Y)
    return try_queens(board, N)
}

Если немного подумать о проблеме, вы поймете, что нет способа разместить N королев на доске, где X <N или Y <N, потому что для этого потребуется, чтобы по крайней мере две королевы оказались в одном ранге или файле, и поэтому они будут атаковать друг друга. Если вы прочтете о проблеме n-queens, вы быстро поймете, что всегда можно разместить N ферзей на NxN для N> 3. Теперь мы знаем, что ответ НЕТ для (X <N или Y <N) и ДА для (X> = N и Y> = N, N> 3). Все, что осталось, это особые случаи:

  • N = 1 (ДА)
  • N = 2 (ДА для X> = 2 и Y> 2 или наоборот)
  • N = 3 (ДА для X> = 3 и Y> 3 или наоборот)

Так что теперь наша хорошая рекурсивная функция становится простой функцией, которая просто сравнивает N с X и Y и возвращает стандартный результат. Это здорово с точки зрения производительности, так как вы можете получить ответ в постоянное время. Это не так здорово с точки зрения программирования, потому что в этот момент вы понимаете, что вопрос действительно больше в том, насколько хорошо вы можете решать головоломки, чем в том, как вы можете написать рекурсивную функцию.

(И, боже, боже, я действительно надеюсь, что я не совершил глупой ошибки в своем ответе на умные штаны. ;-)

Калеб
источник
That's great from a performance point of view, since you can get an answer in constant time. It's not so great from a programming point of view because you realize, at this point, that the question is really more about how well you can solve puzzles than it is about your ability to write a recursive function.Я действительно думаю, что интервьюер ждал этого решения O (1), потому что оно в конечном итоге лучше и не очевидно для многих людей. Проблема nxn queen есть во всех курсах программирования как упражнение для рекурсии - многие люди не будут думать глубже, когда снова увидят эту проблему.
Сопель
4

Если интервьюер попросил вас написать код проблемы, то я думаю, что это несправедливо. Алгоритм требует работы. Однако, если идея состояла в том, чтобы показать интервьюеру классы, методы или некоторые концепции, которые вам нужно использовать, или что-то подобное, то это может быть справедливым вопросом.

Эта проблема является классической проблемой информатики и обсуждается во многих таких книгах. Отличное объяснение, с анимацией и 12 различными решениями вместе с некоторым кодом, можно найти здесь:

http://en.wikipedia.org/wiki/Eight_queens_puzzle

Также код можно найти здесь: http://www.codeproject.com/KB/java/EightQueen.aspx

Не переживайте по этому поводу, как я уже сказал, это не легко.

Без шансов
источник
0

На самом деле это скорее комментарий, но он там не вписывается ...

Шахматная доска имеет 8х8 квадратов, не больше и не меньше (эти вопросы всегда раздражают меня таким подходом к шахматной доске).

Но в любом случае, если у вас есть х * у шахматная доска и n ферзей, и вы берете, что королева "забирает" эти поля

введите описание изображения здесь

не могли бы вы просто создать двумерный массив и «пометить» все поля, на которые нападает одна королева. Затем поместите другой (с середины доски), отметьте оставшиеся поля и т. Д., Пока не запустите ни одно из полей или ферзей.

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

Хм, только что нашел это - проблема 8 королев.

ладья
источник
Сначала я предложил этот точный алгоритм, но учтите, что вам не гарантировано, что если вы воспользуетесь этим подходом, и у вас не останется места, где вы могли бы поставить свою последнюю Королеву, которую вы действительно определили, это невозможно. Вы только исключили эту конкретную договоренность. Это в основном приложение эвристики ближайшего соседа.
Интервью
@ Interviewviewee - Да, я знаю. Это всего лишь то, о чем я думал с макушки головы. Как уже говорилось, это интересная проблема и, возможно, ее можно улучшить, но в 4 часа утра (здесь) мне просто лень думать. Кстати, как прошло интервью?
Ладья
@ Intervieweeee, это правильная идея. Не хватает только того, что если вы обнаружите, что нет места для последней королевы, вы отступаете и пробуете другую позицию для второй и последней королевы. Если для этой королевы нет места, позволяющего разместить последнюю королеву, вы создаете резервную копию на другом уровне и пробуете другое место для третьей до последней королевы и так далее.
Калеб
Мне нравится, что твой аватар - шахматная фигура :)
Уоррен
0

По сути, алгоритм возврата работает так:

  1. Создайте массив X by Y Установите все квадраты пустыми.

  2. Установить счет королевы на ноль.

  3. Установите текущую позицию на (1,1)

  4. Посмотрите, сможете ли вы поместить королеву в текущую позицию.

  5. Если вы можете, установите Array (X, Y) в значение queen, увеличивайте количество ферзей. Если вы разместили всю королеву, остановитесь , у вас есть решение.

  6. Если текущая позиция не (X, Y), увеличьте текущую позицию и перейдите к шагу 4.

  7. Найдите ферзя в последней позиции (той, которая идет последней в порядке увеличения позиций). Установите текущую позицию в положение этой королевы, удалите ее и уменьшите счет ферзя.

  8. Если число ферзей равно нулю, остановитесь , решения не существует.

  9. Увеличить текущую позицию.

  10. Переходите к шагу 4.

Дэвид Шварц
источник
В этом описании алгоритм не отслеживает корректно: он удаляет только последнюю помещаемую ферзь; Вы рискуете никогда не пробовать более ранние королевы на других позициях.
Каспер ван ден Берг
@KaspervandenBerg Алгоритм корректно возвращается. Я бы ответил прямо на вашу критику, но я, честно говоря, не могу этого понять. Я не знаю, что вы подразумеваете под "последней размещаемой королевой". Он удалит только последнюю помещенную королеву, но любая королева может стать последней размещенной, после того как королевы были размещены после ее удаления. Он будет возвращаться по мере необходимости, удаляя королев в обратном порядке, в котором они были размещены.
Дэвид Шварц
0

Добавление к другим ответам: создание двумерного массива только усложняет код.

Вам просто нужен вектор 8 размера для обычной шахматной доски. Или 8 + 1, если, как и C, 1-я позиция равна 0, только для упрощения кода и обработки 1-8, а не 0-7.

Если вы думаете, что x - это ваша позиция в массиве, а y - это содержимое позиции. например, доска [1] = 8 означает, что первая ферзь находится в [1,8].

Таким образом, вам нужно только проверить проверку столбцов.

Во время обучения на факультете я натолкнулся на очень старую книгу (60-е годы?) Об алгоритмах, реализованных в Dartmouth BASIC, в которых реализована задача 8 ферзей с использованием как можно меньшего количества памяти (будучи таким старым, это имеет смысл).

Насколько я помню, он использовал векторную идею, и он по сути грубо форсировал все позиции на доске с двумя циклами FOR. Для проверки правильности положения использовался третий цикл, цикл WHILE в каждой позиции возвращается в вектор и проверяется на равное число или на формулу, использующую касательную операцию для проверки диагоналей.

К сожалению, я потерял след этой книги ...

Указанный алгоритм нашел все решения проблемы n-ферзя.

Руи Ф Рибейро
источник
0

Если вам просто нужно написать алгоритм, чтобы определить, существует ли такая договоренность, посмотрите на существующее исследование:
головоломка «Восемь королев» в Википедии .

Вы можете тривиально вернуть false, если N> min (X, Y).
Прочитав эту страницу, вы узнаете, что возвращаете true, если N <= min (X, Y) и 2, 3! = Min (X, Y).

Что оставляет 2, 3 == min (X, Y) и N <= min (X, Y).

Хорошо, если N <min (X, Y), найти решение тривиально.
Если N == min (X, Y), есть только решение, если max (X, Y)> N.

f(X, Y, N)
    if X < Y => f(Y, X, N)
    if Y > N => false
    => (Y < N) or (Y != 2 and Y != 3) or (X > N)
Deduplicator
источник
0

Очевидно, что решения не существует, если N> min (X, Y). В противном случае вы можете легко показать, что не существует решения для N = X = Y = 2, N = X = Y = 3. Для всех остальных случаев, кажется, есть решение. Число решений, кажется, растет с ростом N.

Вы можете найти решение с помощью исчерпывающего поиска с обратным отслеживанием: поместите ферзь в первый ряд, столбец 1. Поместите ферзь во второй ряд, в первый столбец, которого не может достичь королева в строке 1. Поместите ферзя во второй ряд и т. Д. Если ферзь не может быть помещен в строку k, то вы удалите его и переместите ферзь в строке k-1 в следующую незанятую позицию.

gnasher729
источник