51. N-Queens

Задача

Разместите n ферзей на доске n×n так, чтобы они не били друг друга. Верните все различные расстановки.

Примеры

Пример 1

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Пояснение

У задачи 4 ферзей есть два различных решения.

Пример 2

Input: n = 1
Output: [["Q"]]

Решение

Решение

/**
 * Сложность по времени: O(N!)
 *   В первой строке у нас N вариантов, во второй N-2 (примерно), и т.д.
 *   Это классическая факториальная сложность, так как мы генерируем перестановки.
 *
 * Сложность по памяти: O(N)
 *   Мы храним 3 Set-а размером N и стек рекурсии глубиной N.
 *   Сами доски в ответе занимают место, но вспомогательная память — линейная.
 */
var solveNQueens = function(n) {
    const result = [];
 
    // Используем Set для мгновенной проверки конфликтов
    const cols = new Set(); // Занятые колонки |
    const posDiag = new Set(); // Занятые диагонали / (row + col)
    const negDiag = new Set(); // Занятые диагонали \ (row - col)
 
    // boardState хранит индекс колонки для каждой строки. 
    // Например, [1, 3, 0, 2] для n=4
    const boardState = [];
 
    const backtrack = (row) => {
        // Базовый случай: если мы дошли до row == n, значит, 
        // мы успешно расставили всех королев
        if (row === n) {
            // Превращаем массив индексов в массив строк (формат вывода)
            const board = boardState.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1));
            result.push(board);
            return;
        }
 
        // Пробуем поставить королеву в каждую колонку текущей строки
        for (let col = 0; col < n; col++) {
            // Проверка: бьет ли кто-то эту клетку?
            if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
                continue; // Эта клетка под ударом, пропускаем
            }
 
            // 1. Ставим королеву (регистрируем конфликты)
            cols.add(col);
            posDiag.add(row + col);
            negDiag.add(row - col);
            boardState.push(col);
 
            // 2. Идем глубже
            backtrack(row + 1);
 
            // 3. Бектрекинг: убираем королеву, чтобы попробовать следующую колонку
            cols.delete(col);
            posDiag.delete(row + col);
            negDiag.delete(row - col);
            boardState.pop();
        }
    };
 
    backtrack(0);
    return result;
};