Загадка восьми ферзей - это хорошо известная задача, цель которой состоит в том, чтобы подсчитать, сколько разных способов разместить 8 ферзей на шахматной доске 8 x 8, чтобы ни одна из них угрожают друг другу (это означает, что ни один из них не занимает одну строку, столбец или диагональ, так что один может захватить другого за один ход).

Проблема восьми ферзей является примером более общей «проблемы n ферзей» - проблемы нахождения количества допустимых решений для размещения n ферзей на доске размером nxn. . Обратите внимание, что n представляет одно и то же число в обоих случаях - количество ферзей должно быть таким же, как количество строк / столбцов на доске.

Это интересная проблема, потому что результаты не полностью предсказуемо масштабируются с размером n. Для n = 5 существует 10 возможных решений. Для n = 6 их всего 4. Для n = 7 мы можем найти до 40 возможных решений! Это делает ее намного более интересной, чем эквивалентная задача с ладьями, в которой количество решений легко вычисляется как n! и поэтому вполне предсказуемо увеличивается с ростом n.

Метод грубой силы

Один из способов решить эту проблему - это вычисление «грубой силы» каждой позиции на доске. Мы могли бы начать с верхнего левого угла (а8, как я полагаю, на языке шахматистов) и поставить там ферзя. Таким образом, нашей целью было бы исчерпать все возможные состояния доски, в которых участвует первый ферзь в верхнем левом углу, прежде чем двигаться дальше. Поэтому мы найдем первое возможное место, чтобы поставить вторую ферзя. Продолжая расставлять ферзей, мы должны проверить все возможные состояния доски, в которых второй ферзь находится в этой позиции (и первый ферзь в верхнем левом углу), прежде чем перемещать второго ферзя на следующую возможную позицию. После того, как мы проверили все возможные комбинации для каждого возможного размещения второго ферзя, мы наконец могли быть уверены, что мы испробовали все комбинации, в которых первая ферзь находится в ее верхнем левом углу. Затем мы могли бы переместить первого ферзя на вторую позицию на доске и таким же образом протестировать все возможные комбинации, которые вовлекают ее в это новое место. Мы будем вести постоянный подсчет каждого раза, когда мы находим допустимое решение во время этого процесса, и в конце мы узнаем, сколько возможных состояний платы представляют собой возможное решение.

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

Неудивительно, что это может занять очень много времени для больших значений n. В зависимости от того, как это было реализовано, мы можем тестировать до (n * n) ^ n комбинаций. Но есть еще более серьезная проблема с этим подходом - если он будет реализован, как указано выше, он приведет к дублированию решений. Если бы существовало конкретное решение, включающее ферзя 1 (Q1) в точке a8 и ферзя 2 (Q2) в точке b6, мы бы позже наткнулись на эквивалентное решение. которые включали Q2 в a8 и Q1 в b6. Другими словами, мы будем тестировать перестановки, а не уникальные комбинации. Поэтому нам нужно будет вести учет решений, которые мы нашли на данный момент, чтобы мы могли отбросить любые дубликаты.

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

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

Другой, немного лучший метод грубой силы

Вышеупомянутая стратегия будет работать, но есть еще более эффективные способы решения этой проблемы. Тот факт, что количество ферзей совпадает с количеством клеток на шахматной доске, дает нам явное преимущество. Поскольку имеется только n рядов и n ферзей, отсюда следует, что в допустимом решении будет ровно один ферзь в каждой строке. Если бы в ряду стояли две ферзя, они бы угрожали друг другу, и мы не смогли бы найти верного решения. Если бы какая-либо строка была пустой, нам бы пришлось уместить все n ферзей в оставшиеся (n - 1) строки, что означало бы, что две ферзи будут вынуждены удвоиться подряд, чего они не могут сделать. Отсюда следует, что у нас не может быть действительного решения с какими-либо пустыми строками (то же самое верно и для столбцов, конечно, поэтому не стесняйтесь читать следующие рассуждения и мысленно переключать `` строку '' на `` столбец '', если вы так склонны) .

Что в этом хорошего, так это то, что это означает, что в каждом ряду будет королева. Это означает, что для нашей первой королевы нам фактически не нужно проверять, что произойдет, если мы разместим ее на каждой отдельной позиции на доске. Мы можем эффективно отнести ее к первому ряду и проверить каждую возможную комбинацию, в которой ферзь находится на первой позиции в этом ряду (a8), каждую возможную комбинацию, которая включает ее во второй позиции (b8), и т. Д. Как только мы закончим проверяя каждую комбинацию с этим ферзем в каждом месте в первом ряду (a8-h8), мы узнаем, что мы проверили каждую комбинацию, в которой участвует ферзь в первом ряду. Поскольку мы знаем, что существует n0 комбинаций, в которых в первом ряду нет ферзя (помните - нет пустых рядов!), Мы можем заключить, что проверили каждую возможную уникальную комбинацию доски.

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

Суть в том, что мы должны назначить каждую из наших n ферзей каждой из n строк. Вместо того, чтобы проверять, можно ли каждую фишку поставить на каждое место на доске, мы можем проверить каждую комбинацию, которая включает Q1 в строке 1, Q2 в строке 2, Q3 в строке 3 и так далее. Это уже сужает количество комбинаций, которые нам нужно проверить, до максимального значения n ^ n. Нам не нужно проверять, что произойдет, если мы поместим Q2 в строку 3 и Q3 в строку 2, потому что проверка таких вещей приведет только к дублированию / эквивалентным состояниям платы. Назначая Q2 строке 2 и Q3 строке 3, мы гарантируем, что такие повторяющиеся состояния не могут возникнуть.

Реализация алгоритма

Теперь представьте, что вы пытаетесь реализовать это решение на выбранном вами языке программирования (не стесняйтесь использовать PowerPoint или Super Mario World). Вы можете сохранить представление платы в памяти в виде двухмерного массива и пометить занятые места цифрой 1, а свободные места - 0. Это не оптимальное решение (как будет обсуждаться в более позднем посте). ), но работать будет хорошо.

Вам также понадобится функция для проверки на конфликты. Это будет простой вопрос проверки, поместит ли ферзь в клетку в тот же ряд, столбец или диагональ, что и любые другие ферзя. Диагонали здесь самые хитрые, потому что их больше, чем строк и столбцов, и есть как большие (верхний левый, так и нижний правый), так и второстепенные (верхний правый нижний левый) диагонали.

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

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

Псевдокод для этого будет выглядеть примерно так: