N-Queens II

문제

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:

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

---

풀이

파이썬으로 하루종일 답보고 분석했던 문제다.

같은 행과 대각선에 배치되지 않게 놓을 수 있는 경우의 수를 구하는 문제다.

 

백트래킹, 재귀, 자바스크립트 화살표 함수를 공부할 수 있는 아주 양질의 문제이다.

 

2차원 배열로 (x, y) 형태의 좌표를 이용해서 코드를 짰었는데,

1차 배열로 구현 가능하다.

ex) [2, 0, 3, 1]

이때 배열의 index는 행이 되고 value는 열이 된다.

즉 좌표로 표현하면 (i, arr[i])

 

---

답안

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
  let count = 0;
  let cols = new Set();
  let diag1 = new Set();
  let diag2 = new 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);

      // row값 1 증가시켜서 재귀
      backtrack(row + 1);

      // 볼 일 다 봤으면 제거하고 다음 col로 비교
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  };
  backtrack(0);
  return count;
};