Java. N ферзей, на доске, нужен алгоритм для проверки, «а что, если ферзь может стоять на том же месте» или как найти все способы?

Question

[Dmitry Stoyanov]

Задача: дана шахматная доска NxN. Необходимо поставить на ней N ферзей так, чтобы ни один не угрожал другому. Программа должна выводить все возможные варианты такого расположения.

Проблема собственно в том. Что всё готово, осталось додумать метод расстановки, т.к. мой алгоритм не учитывает того, что ферзь может стоять на одном и том же месте при этом другие ферзи, будут располагаться иначе, т.е. нужно внести "поправку на повторение".
Ещё для примера: программа выполняет условия только для доски не больше 4х4. Если доска 5х5 то выдает в результате выходит 4 способа, хотя на самом деле их должно быть 10.

https://drive.google.com/folderview?id=0B3gMuZG1Lo...

Буду рад увидеть реализацию нужного мне алгоритма.
Спасибо.

Answer 1

[Dmitry Stoyanov]

www.java.achchuthan.org/2012/02/n-queens-problem-i...

Answer 2

[Rsa97]

Самый очевидный алгоритм:
Очевидно, что в одой вертикали или горизонтали не может быть двух ферзей. Таким образом, все варианты можно представить как перестановки N чисел от 1 до N, где позиция числа - это номер вертикали, а само число - номер горизонтали. Остаётся сгенерировать такие перестановки и проверить в них диагонали, если |Pi-Pj| = |i-j|, то ферзи стоят на одной диагонали и позиция недопустима.
Ну а дальше можно оптимизировать алгоритм, проверяя диагонали ещё на стадии генерации перестановок.

Answer 3

[fish72]

программа "QueensProblem.exe" расставляет ферзи на квадратной доске:
https://yadi.sk/d/ZSKQmtIFtVhatw