[LeetCode] 52. N-Queens II

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 the number of distinct solutions to the n-queens puzzle.

Example 1:

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

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

 

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

 

Code :

var totalNQueens = function(n) {
    let count = 0; // 해의 개수를 세기 위한 변수를 초기화합니다.

    const cols = new Set(); // 퀸이 위치한 열을 저장할 Set을 초기화합니다.
    const diag1 = new Set(); // 대각선 방향 (↙↗)의 퀸이 위치한 곳을 저장할 Set을 초기화합니다.
    const diag2 = new Set(); // 대각선 방향 (↘↖)의 퀸이 위치한 곳을 저장할 Set을 초기화합니다.

    // 백트래킹을 수행하는 함수를 정의합니다.
    const backtrack = row => {
        if (row === n) { // 모든 행에 퀸을 배치한 경우
            count++; // 해의 개수를 증가시킵니다.
            return;
        }
        for (let col = 0; col < n; col++) { // 각 열에 퀸을 배치합니다.
            if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) {
                continue; // 충돌이 발생하는 경우 넘어갑니다.
            }
            cols.add(col); // 열에 퀸을 배치합니다.
            diag1.add(row + col); // ↙↗ 방향의 대각선에 퀸을 배치합니다.
            diag2.add(row - col); // ↘↖ 방향의 대각선에 퀸을 배치합니다.
            backtrack(row + 1); // 다음 행에 퀸을 배치합니다.
            cols.delete(col); // 열에 배치된 퀸을 제거합니다.
            diag1.delete(row + col); // ↙↗ 방향의 대각선에 배치된 퀸을 제거합니다.
            diag2.delete(row - col); // ↘↖ 방향의 대각선에 배치된 퀸을 제거합니다.
        }
    };

    backtrack(0); // 백트래킹을 시작합니다.
    return count; // 해의 개수를 반환합니다.
};

 

Solutions Code :

var totalNQueens = function(N) {
    let ans = 0 // 해의 개수를 저장할 변수를 초기화합니다.

    // 재귀적으로 퀸을 배치하는 함수를 정의합니다.
    const place = (i, vert, ldiag, rdiag) => {
        if (i === N) ans++ // 모든 행에 퀸을 배치했을 때, 해의 개수를 증가시킵니다.
        else for (let j = 0; j < N; j++) { // 각 열에 퀸을 배치합니다.
            let vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j) // 각 퀸의 위치에 대한 마스크를 생성합니다.
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue // 충돌이 발생하는 경우 건너뜁니다.
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask) // 다음 행에 퀸을 배치합니다.
        }
    }

    place(0,0,0,0) // 백트래킹을 시작합니다.
    return ans // 해의 개수를 반환합니다.
};

 

 

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

Problems - LeetCode