Здравствуйте, Пономарёв Иван, Вы писали:

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

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