[LeetCode] 51. N-Queens

https://leetcode.com/

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

출처 : https://leetcode.com/problems/n-queens/

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

 

Example 2:

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

 

Constraints:

• 1 <= n <= 9

 

Code :

/*
    1. solveNQueens 함수는 N-Queens 문제를 해결하는 함수입니다. n은 보드 크기입니다.
    2. results 배열은 모든 가능한 해결책을 저장할 곳입니다.
    3. board 배열은 현재의 보드 상태를 저장합니다. 처음에는 모든 위치가 비어 있습니다.
    4. isSafe 함수는 주어진 행과 열에 퀸을 배치할 수 있는지를 확인합니다. 다른 퀸과 겹치지 않도록 검사합니다.
    5. solve 함수는 백트래킹을 수행합니다. 각 행에 대해 가능한 열에 퀸을 배치하고, 이를 재귀적으로 반복합니다.
    6. solve 함수를 호출하여 가능한 모든 배치를 시도하고, 유효한 경우 결과에 추가합니다.
*/
var solveNQueens = function(n) {
    const results = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    const isSafe = (row, col) => {
        // 현재 행 위의 열을 확인합니다.
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false;
            }
        }
        // 왼쪽 위 대각선을 확인합니다.
        for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') {
                return false;
            }
        }
        // 오른쪽 위 대각선을 확인합니다.
        for (let i = row, j = col; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') {
                return false;
            }
        }
        return true;
    };
    const solve = (row) => {
        if (row === n) {
            // 모든 행이 채워졌다면 현재 보드를 결과에 추가합니다.
            results.push(board.map(row => row.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q'; // 퀸을 배치합니다.
                solve(row + 1); // 다음 행으로 넘어갑니다.
                board[row][col] = '.'; // 백트래킹합니다.
            }
        }
    };
    solve(0); // 첫 번째 행부터 시작합니다.
    return results;
};

 

Solutions Code :

var solveNQueens = function(n, start = 0, mat) {
    // N x N 크기의 체스판을 나타내는 이차원 배열 초기화
    var mat = [...new Array(n)].map(ele => new Array(n).fill("."));
    // 체스판의 한 변의 길이
    var len = mat.length;
    // 결과를 저장할 배열
    var result = [];
    // 퀸의 배치 경우의 수를 카운트하는 변수
    var count = 0;
    // 백트래킹을 수행하는 helper 함수
    helper(0, mat);
    // 최종적으로 찾은 퀸의 배치 결과 반환
    return result;
    
    function helper(row, mat) {
        // 모든 행에 퀸을 배치한 경우, 현재 퀸의 배치를 결과에 추가하고 종료
        if (row == n) {
            result.push([...mat].map(ele => ele.join("")));
            return;
        }
        // 현재 행에서 가능한 모든 열에 대해 시도
        for (let j = 0; j < len; j++) {
            // 대각선 상에 다른 퀸이 없는 경우에만 퀸 배치 시도
            if (checkDigonal(row, j, mat, n)) {
                // 현재 위치에 퀸 배치
                mat[row][j] = 'Q';
                // 다음 행으로 재귀 호출
                helper(row + 1, mat);
                // 백트래킹: 퀸 배치를 취소하고 다른 경우를 탐색
                mat[row][j] = '.';
            }
        }
    }
};

// 대각선 상에 다른 퀸이 있는지 확인하는 함수
function checkDigonal(i, j, mat, len) {
    var x = i - 1;
    var y = j - 1;
    // 왼쪽 위 대각선 확인
    while (x >= 0 && x < len && y >= 0 && y < len) {
        if (mat[x][y] == 'Q') return false;
        x = x - 1;
        y = y - 1;
    }
    x = i - 1;
    y = j + 1;
    // 오른쪽 위 대각선 확인
    while (x >= 0 && x < len && y >= 0 && y < len) {
        if (mat[x][y] == 'Q') return false;
        x = x - 1;
        y = y + 1;
    }
    x = i - 1;
    y = j;
    // 위쪽 확인
    while (x >= 0 && x < len && y >= 0 && y < len) {
        if (mat[x][y] == 'Q') return false;
        x--;
    }
    // 대각선 상에 다른 퀸이 없으면 true 반환
    return true;
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode