Задача о ферзях

На доске $n \times n$ расставить $n$ ферзей так, чтобы никакие два не били друг друга. Ферзь бьёт по горизонтали, вертикали и обеим диагоналям.

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

Доска — это перестановка

Первое наблюдение снимает половину задачи. Ферзей ровно $n$, строк тоже $n$, а в одной строке двух ферзей быть не может — значит, в каждой строке ровно один ферзь. То же для столбцов.

Следовательно, расстановка полностью описывается массивом $c_0, \dots, c_{n-1}$, где $c_i$ — столбец ферзя в строке $i$, и этот массив — перестановка.

Вместо перебора $\binom{n^2}{n}$ расстановок (для $n = 8$ это $4 \cdot 10^9$) мы перебираем $n!$ перестановок ($40\,320$). Пять порядков разницы — и всё из одного наблюдения.

Это общий приём: прежде чем писать перебор, найдите представление, в котором заведомо неверные варианты не существуют.

Диагонали

Осталось проверить диагонали. Ферзи в строках $i$ и $j$ бьют друг друга по диагонали, когда

$$i - c_i = j - c_j \quad\text{или}\quad i + c_i = j + c_j$$

Первое — диагонали «вниз-вправо», второе — «вниз-влево». Эквивалентная запись, которую чаще пишут в коде: $|c_i - c_j| = |i - j|$.

Проверять в конце или на лету

Вариант первый: сгенерировать все перестановки и каждую проверить.

// перебрали перестановку целиком, теперь проверяем
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (abs(col[i] - col[j]) == j - i) return false;

Стоимость: $n! \cdot n^2$. Для $n = 8$ это около трёх миллионов операций — пройдёт. Для $n = 10$ уже $3.6 \cdot 10^8$ — на грани.

Вариант второй: проверять каждого ферзя сразу при постановке и не спускаться в заведомо плохую ветку.

void place(int row) {
    if (row == n) { answer++; return; }
    for (int c = 0; c < n; c++) {
        bool ok = true;
        for (int r = 0; r < row; r++)
            if (col[r] == c || abs(col[r] - c) == row - r) { ok = false; break; }
        if (!ok) continue;
        col.push_back(c);
        place(row + 1);
        col.pop_back();
    }
}

Здесь отпала даже надобность в массиве «использовано»: проверка col[r] == c заодно ловит и повтор столбца.

Второй вариант быстрее по двум причинам сразу: проверка короче (сравниваем нового ферзя только с уже поставленными) и, главное, целые поддеревья не обходятся. Конфликт, найденный на второй строке, отсекает $(n-2)!$ вариантов.

Проверено: количество расстановок для $n$ от 1 до 10 равно 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 — это известная последовательность, и она совпала.

Обратите внимание на нули при $n = 2$ и $n = 3$: расстановок не существует. Хороший тест — код, забывший про диагонали, выдаст здесь 2 и 6.

Ускорение через множества занятых

Внутренняя проверка стоит $O(n)$. Её можно сделать за константу, если хранить три массива занятости: по столбцам и по двум диагоналям.

Диагональ «вниз-вправо» нумеруется числом $i - c + n$ (сдвиг, чтобы индекс был неотрицательным), «вниз-влево» — числом $i + c$.

vector<char> usedCol(n), usedDiag1(2 * n), usedDiag2(2 * n);

void place(int row) {
    if (row == n) { answer++; return; }
    for (int c = 0; c < n; c++) {
        int d1 = row - c + n, d2 = row + c;
        if (usedCol[c] || usedDiag1[d1] || usedDiag2[d2]) continue;
        usedCol[c] = usedDiag1[d1] = usedDiag2[d2] = 1;
        place(row + 1);
        usedCol[c] = usedDiag1[d1] = usedDiag2[d2] = 0;
    }
}

Три установки перед спуском и три снятия после — тот же ритуал «изменить, углубиться, откатить», что и в остальных переборах.

Дальше это ускоряется до битовых масок: три числа вместо трёх массивов, и ~(cols | diag1 | diag2) сразу даёт множество допустимых столбцов. Так задача решается до $n \approx 17$ за разумное время.

Чему учит задача

Три вывода, полезные далеко за её пределами:

1. Представление важнее алгоритма. Переход от «клеток» к «перестановке» дал пять порядков, а перебор остался тем же.
2. Проверять надо как можно раньше. Отсечение на второй строке ценнее любой оптимизации проверки на восьмой.
3. Инкрементальная проверка бьёт полную. Не пересчитывайте всё состояние — поддерживайте его.

И практическое: количество расстановок для малых $n$ известно и легко гуглится. Это готовый набор тестов, которым стоит проверить решение до отправки.