Алгоритм N+1 ферзя

Я хочу улучшить скорость моего алгоритма для вычисления количества решений проблемы N+1 ферзей (поместите N+1 ферзей на NxN шахматную доску с 1 пешкой). Я в основном использую брутфорс в сочетании с откатом, я сначала ставлю пешку на случайное место на доске (без краев и углов квадрата без краев) и только после этого начинаю расставлять ферзей с откатом. Этот метод простой, но и медленный. Какие алгоритмы будут быстрее?

Я думал сначала поставить пешку и 4 ферзя с каждой стороны от пешки, но не уверен, что это улучшит скорость расчета.


algorithm backtracking enumeration brute-force n-queens
person user2295594    schedule 18.04.2013    source источник
comment
Рассматривали ли вы возможность сформулировать ее как задачу с ограничениями и решить ее с помощью стандартного CP-решателя?   -  person Lars Kotthoff    schedule 18.04.2013
comment
Это проблема, которая требует больше бумаги, пера и логики, чем грубой силы.   -  person Sulthan    schedule 18.04.2013
comment
Сам по себе это не очень хороший ответ, но на странице википедии описано множество оптимизаций для этой проблемы.   -  person Dan Puzey    schedule 18.04.2013
comment
Я не уверен, что понимаю проблему. Вы хотите, чтобы ферзи не атаковали друг друга или все ферзи не атаковали пешку?   -  person Sulthan    schedule 18.04.2013
comment
Задача с 8 ферзями отличается от той, которую я пытаюсь решить.   -  person user2295594    schedule 18.04.2013

Ответы (2)


arrow_upward
3
arrow_downward

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

person Ivaylo Strandjev    schedule 18.04.2013
comment
Только хотел написать то же самое. Используя повороты, он может сразу уменьшить возможности в 4 раза. - person Sulthan; 18.04.2013
comment
Фактор 8 на самом деле, вы также можете зеркально отразить диагонали. - person TemplateRex; 18.04.2013

arrow_upward
0
arrow_downward

Ваше собственное предложение звучит правильно, поскольку оно начинается с основного ограничения, которому должно удовлетворять любое решение, а не проверяется постфактум для каждого решения-кандидата.

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

Позиция пешки на доске NxN может быть уменьшена до внутренней поддоски (N-2)x(N-2), и вы можете использовать 8-кратное вращение/зеркальную симметрию, чтобы еще больше уменьшить ее до одного из октантов этого внутреннего квадрата.

person TemplateRex    schedule 18.04.2013