Мне задали следующий вопрос в сегодняшнем интервью, и я с тех пор об этом думаю. Я не смог ответить на него и не смог найти решение онлайн.
Учитывая шахматную доску с размерами X от Y и N королев, определите, можно ли расположить этих королев на доске так, чтобы они не могли атаковать друг друга.
Доска 2 x 3 с 2 ферзями имеет решение, поэтому алгоритм вернет true:
Q . .
. . Q
Я ищу программный подход к этой головоломке, а не просто способы ее решения, например, на бумаге.
algorithms
puzzles
chess
интервьюируемый
источник
источник
Ответы:
Это (IMO) не очень интересная проблема с точки зрения программирования. Вы могли бы придумать рекурсивный алгоритм, который пробует каждое расположение, что-то вроде этого:
Если немного подумать о проблеме, вы поймете, что нет способа разместить N королев на доске, где X <N или Y <N, потому что для этого потребуется, чтобы по крайней мере две королевы оказались в одном ранге или файле, и поэтому они будут атаковать друг друга. Если вы прочтете о проблеме n-queens, вы быстро поймете, что всегда можно разместить N ферзей на NxN для N> 3. Теперь мы знаем, что ответ НЕТ для (X <N или Y <N) и ДА для (X> = N и Y> = N, N> 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 есть во всех курсах программирования как упражнение для рекурсии - многие люди не будут думать глубже, когда снова увидят эту проблему.Если интервьюер попросил вас написать код проблемы, то я думаю, что это несправедливо. Алгоритм требует работы. Однако, если идея состояла в том, чтобы показать интервьюеру классы, методы или некоторые концепции, которые вам нужно использовать, или что-то подобное, то это может быть справедливым вопросом.
Эта проблема является классической проблемой информатики и обсуждается во многих таких книгах. Отличное объяснение, с анимацией и 12 различными решениями вместе с некоторым кодом, можно найти здесь:
http://en.wikipedia.org/wiki/Eight_queens_puzzle
Также код можно найти здесь: http://www.codeproject.com/KB/java/EightQueen.aspx
Не переживайте по этому поводу, как я уже сказал, это не легко.
источник
На самом деле это скорее комментарий, но он там не вписывается ...
Шахматная доска имеет 8х8 квадратов, не больше и не меньше (эти вопросы всегда раздражают меня таким подходом к шахматной доске).
Но в любом случае, если у вас есть х * у шахматная доска и n ферзей, и вы берете, что королева "забирает" эти поля
не могли бы вы просто создать двумерный массив и «пометить» все поля, на которые нападает одна королева. Затем поместите другой (с середины доски), отметьте оставшиеся поля и т. Д., Пока не запустите ни одно из полей или ферзей.
Это, конечно, очень упрощенный подход, так как, если я поставлю его неправильно, я соберу максимальное число ферзей.
Хм, только что нашел это - проблема 8 королев.
источник
По сути, алгоритм возврата работает так:
Создайте массив X by Y Установите все квадраты пустыми.
Установить счет королевы на ноль.
Установите текущую позицию на (1,1)
Посмотрите, сможете ли вы поместить королеву в текущую позицию.
Если вы можете, установите Array (X, Y) в значение queen, увеличивайте количество ферзей. Если вы разместили всю королеву, остановитесь , у вас есть решение.
Если текущая позиция не (X, Y), увеличьте текущую позицию и перейдите к шагу 4.
Найдите ферзя в последней позиции (той, которая идет последней в порядке увеличения позиций). Установите текущую позицию в положение этой королевы, удалите ее и уменьшите счет ферзя.
Если число ферзей равно нулю, остановитесь , решения не существует.
Увеличить текущую позицию.
Переходите к шагу 4.
источник
Добавление к другим ответам: создание двумерного массива только усложняет код.
Вам просто нужен вектор 8 размера для обычной шахматной доски. Или 8 + 1, если, как и C, 1-я позиция равна 0, только для упрощения кода и обработки 1-8, а не 0-7.
Если вы думаете, что x - это ваша позиция в массиве, а y - это содержимое позиции. например, доска [1] = 8 означает, что первая ферзь находится в [1,8].
Таким образом, вам нужно только проверить проверку столбцов.
Во время обучения на факультете я натолкнулся на очень старую книгу (60-е годы?) Об алгоритмах, реализованных в Dartmouth BASIC, в которых реализована задача 8 ферзей с использованием как можно меньшего количества памяти (будучи таким старым, это имеет смысл).
Насколько я помню, он использовал векторную идею, и он по сути грубо форсировал все позиции на доске с двумя циклами FOR. Для проверки правильности положения использовался третий цикл, цикл WHILE в каждой позиции возвращается в вектор и проверяется на равное число или на формулу, использующую касательную операцию для проверки диагоналей.
К сожалению, я потерял след этой книги ...
Указанный алгоритм нашел все решения проблемы n-ферзя.
источник
Если вам просто нужно написать алгоритм, чтобы определить, существует ли такая договоренность, посмотрите на существующее исследование:
головоломка «Восемь королев» в Википедии .
Вы можете тривиально вернуть 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.
источник
Очевидно, что решения не существует, если N> min (X, Y). В противном случае вы можете легко показать, что не существует решения для N = X = Y = 2, N = X = Y = 3. Для всех остальных случаев, кажется, есть решение. Число решений, кажется, растет с ростом N.
Вы можете найти решение с помощью исчерпывающего поиска с обратным отслеживанием: поместите ферзь в первый ряд, столбец 1. Поместите ферзь во второй ряд, в первый столбец, которого не может достичь королева в строке 1. Поместите ферзя во второй ряд и т. Д. Если ферзь не может быть помещен в строку k, то вы удалите его и переместите ферзь в строке k-1 в следующую незанятую позицию.
источник