n-queens.md

N Queens

Oct 12, 2020 · 4 min read

Найти все варианты расстановки N ферзей на шахматной доске размером NxN так, чтобы ни одна из фигур не была под боем другой.

Одни из примеров такой расстановки на доске размером 8x8:

На вход даётся N, нужно вернуть все возможные варианты таких расстановок.

Пример для N = 4:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Q означает ферзя, а . – пустую клетку.

Задача на LeetCode.

Решение #

Отношение лайков к дизлайкам намекает, что задача хорошая:

Так и есть, это классическая задача на backtracking.

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

Например, для обычной доски (N = 8) оно равно: 64!/(8!(64-8)!) ~= 4,426,165,368, а количество расположений, которое удовлетворяет заданным ограничениям, всего 92!

В этом и заключается суть бектрекинга — обходить не всё дерево возможных вариантов, а сразу отрезать те пути, которые заведомо не приведут к решению.

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

Алгоритм примерно следующий.

Ставим первого ферзя на первую клетку в первом ряду. Далее пробуем поставить следующего ферзя на второй ряд, т.к. весь первый ряд находится под ударом первого ферзя. Ставим на первую клетку и… понимаем, что ферзь под ударом, а значит это «мёртвая» ветка дерева, по которой идти точно не стоит.

Ставим второго ферзя на вторую клетку, третью и так далее, пока не найдётся «правильная» клетка в этом ряду. И так далее с k-м ферзём в k-м ряду — на каждом шаге необходимо проверять расстановку на «валидность».

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const result = [];
    const board = [];

    // будем рекурсивно вызывать dfs,
    // обходя дерево возможных вариантов
    // в board будет хранится тещущее состояние,
    // в result — накапливаться результат
    dfs(n, board, result);
    return result;
};

/**
 * Рекурсивно обходит дерево возможных вариантов,
 * постепенно заполняя массив ответов, переданный по ссылке.
 * @param {number} n
 * @param {number[]} board
 * @param {string[][]} result
 * @return {void}
 */
function dfs(n, board, result) {
    // выход из рекурсии:
    // заполнили всю доску n фигурами,
    // значит надо включить конфигурацию в ответ,
    // не забыв сериализовать в нужную по формату строку
    if (board.length === n) {
        result.push(serialize(board));
    } else {
        // бежим по всем колонкам и
        // пытаемся поставить фигуру так,
        // чтобы положение относительно
        // других фигур было валидным
        for (let i = 0; i < n; i++) {
            // кладём очередную фигуру
            board.push(i);
            // проверяем не бьют ли ферзи друг друга
            if (valid(board)) {
                // если нашли валидное положение
                // двигаемся дальше, а именно
                // пробуем поставить следующего ферзя
                // на новом ряду
                dfs(n, board, result);
            }
            // при выходе из рекурсии
            // снимаем последнего ферзя
            board.pop();
        }
    }
}

/**
 * Проверяет поле на валидность,
 * т.е. что ферзи не бьют друг друга.
 * @param {number[]} board
 * @return {boolean}
 */
function valid(board) {
    const queenY = board.length - 1;
    const queenX = board[board.length - 1];

    // проверяем всех ферзей НЕ включая последнего
    for (let y = 0; y < queenY; y++) {
        // (x, y) - текущий ферзь
        // (queenX, queenY) – последний ферзь
        const x = board[y];
        const dx = Math.abs(queenX - x);
        const dy = queenY - y;

        // бьют друг друга если:
        // dx == 0  – стоят на одной вертикали
        // dx == dy – стоят на одной диагонали
        if (dx == 0 || dx == dy) {
            return false;
        }
    }
    // Проверили, что ни один ферзь
    // не бьёт последнего.
    // Так же мы проверяли на предыдущих
    // рекурсивных вызовах,
    // т.е. для каждого ферзя верно, что
    // он не бьёт предыдущих себе,
    // а значит и всё поле валидное
    return true;
}

/**
 * Сериализует указанное расположение ферзей
 * в строку, согласно формату ответа.
 * @param {number[]} board
 * @return {string}
 */
function serialize(board) {
    return board.map((queenX) => {
        const row = [];
        for (let x = 0; x < board.length; x++) {
            row.push(x === queenX ? 'Q' : '.')
        }
        return row.join('');
    });
}

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

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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