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

Имеет смысл располагать только по одному ферзю в столбце, т. е. искать решение в виде f(i), i = 1..N, 1<=f<=N.

Создадим матрицу a[i, j], значением элемента которой будет количество ферзей, под ударом которых находится поле (i, j). Тогда при выборе строки для i-го столбца мы будем выбирать только ту, для которой a[i, j] = 0. Инкрементируем значения a[i,j] "ферзевым паттерном". Если на каком-то шаге в текущем столбце нечего выбрать -- приехали, отматываем алгоритм назад, декрементируем матрицу Есть гипотеза, что в связи с быстрым "забиванием" матрицы ненулевыми элементами, такой алгоритм сойдется за малое (не экспоненциально зависящее от N) время.