検索ルール

1.上、下|左、右

2. Positive Diagonal

3. Negative Diagonal

問題を解く

上の3つのルールを使って問題を解くことができます。

for (let i = 0; i < n; i++) {
	// 각 index마다 Q을 배치했다고 가정하고 연산 후 넘어간다.
	// 이는 첫 번째 행에 대한 배치이다.
}

for (let i = 0; i < n; i++) {
  const col = new Set();
  const pos = new Set();
  const neg = new Set();

  col.add(i);
  pos.add(0 - i);
  neg.add(0 + i);
}

const dfs = (r, n, col, pos, neg) => {
    if (r === n) {
			// 모든 행을 검사했을 때 처리
    } else {
			// DFS의 파라미터로 행(r)을 전달해주고, 열(c)은 for 문으로 순회하면서 확인한다.
      for (let c = 0; c < n; c++) {

				// 만약 상하, pos, neg 방향에 Queen이 존재하면 다음 열로 넘어간다.
        if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
          continue;
        }
				
				// 겹치지 않으면 해당 위치에서의 상하, pos, neg 포지션을 Set 객체에 추가하고,
				// 다음 행으로 넘어간다.(재귀 호출한다.)
        col.add(c);
        pos.add(r - c);
        neg.add(r + c);
        dfs(r + 1, n, col, pos, neg);

				// DFS를 재귀 호출한 후 다음 행을 확인하기 위해 다시 delete 해준다.
        col.delete(c);
        pos.delete(r - c);
        neg.delete(r + c);
      }
    }
  };

完了したコード

const solution = (n) => {
  let answer = 0;

  const dfs = (r, n, col, pos, neg) => {
    if (r === n) {
      answer += 1;
    } else {
      for (let c = 0; c < n; c++) {
        if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
          continue;
        }

        col.add(c);
        pos.add(r - c);
        neg.add(r + c);
        dfs(r + 1, n, col, pos, neg);
        col.delete(c);
        pos.delete(r - c);
        neg.delete(r + c);
      }
    }
  };

  for (let i = 0; i < n; i++) {
    const col = new Set();
    const pos = new Set();
    const neg = new Set();
    col.add(i);
    pos.add(0 - i);
    neg.add(0 + i);

    dfs(1, n, col, pos, neg);
  }

  return answer;
};