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