[Algorithm] 백준 9663 (javaScript)

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

문제 해결

먼저 체스 자체를 잘 몰라서 난관이였다 ;;
퀸의 움직임은 상하좌우, 대각선 8방으로 무한정 이동이 가능하다.
즉 행을 기준으로 퀸을 배치한다고 하면,
퀸을 배치할때마다 같은 열 (상하), 같은 행 (좌우), 대각선을 체크하여
N행까지 배치가 성공하면 cnt를 증가시킨다.

const N = require("fs").readFileSync("/dev/stdin") * 1;

const arr = new Array(N).fill(0);
let answer = 0;

const isValid = (col) => {
  for (let i = 0; i < col; i++) {
    if (arr[col] === arr[i] || col - i === Math.abs(arr[col] - arr[i]))
      return false;
  }
  return true;
};

const setQueen = (col) => {
  if (col == N) {
    answer++;
    return;
  }

  for (let i = 0; i < N; i++) {
    arr[col] = i;
    if (isValid(col)) setQueen(col + 1);
  }
};

setQueen(0);
console.log(answer);

BOJ 9663