[Algorithm] N-Queens, N 퀸즈, N개의 여왕, N 여왕

DFS ( Depth-first search ) 의 꽃인 N queens 를 구현하였다. 물론 자의로 주어진 스켈레톤에 구현하였고, 타의로 내 레포지토리에 하나가 쌓이게 되었다. 우선 N queens를 구현하기에 앞서, BFS 와 DFS를 모른다면 이 링크를 통해 개념 정도는 숙지를 해두자.

[Algorithm] BFS, DFS - 너비우선탐색, 깊이우선탐색

 

 

Backtracking ( 백트래킹, 퇴각검색 )

백트래킹은 한정 조건을 가지는 문제를 푸는 전략이며, DFS의 백트래킹은 단연 검사할 필요가 없는 행을 과감히 포기하는 것이다.

 

가령 아래와 같은 체스판이 있는 경우, 퀸이 놓인 자리를 1이라 하자.

[

   [ 1, 0, 0, 0 ],

   [ 0, 0, 0, 0 ],

   [ 0, 0, 0, 0 ],

   [ 0, 0, 0, 0 ]

]

이 체스판에서 퀸이 놓인 자리를 기준으로 놓여있는 퀸에게 공격받지 않으려면 퀸이 갈 수 있는 모든 경로 위에 있는 곳을 없다고 가정하면 된다.

 

이게 N queens 문제를 풀기위한 핵심전략이다.

 

N-Queens ( N 퀸즈 )

N개의 퀸을 N*N의 체스판 위에 서로 공격하지 못하는 모든 경우의 수를 찾는 알고리즘 문제이다.

 

우리의 전략은 간단하다.

1. NxN의 보드를 만들고 0으로 채운다
2. 지금의 위치에 퀸을 놓는다
3. conflict가 발생했는 지 검사한다.
4. conflict ? 다시 뺀다 : 재귀호출(row+1)
5. 1~4를 n/2 실시한다

※ n%2 === 0 이면, 가운데를 기준으로 퀸의 위치가 대칭이다

※ n%2 === 1 이면, 한 번 더 백트래킹을 실행한다

※ n < 4 이면, 예외처리

 

먼저 예외처리를 보자.

n = 0 인 경우는 항상 솔루션이 1개이다. 그 솔루션은 '없다' 이다.

n = 1 인 경우는 항상 솔루션이 1개이다. 마찬가지로, 그냥 한 칸에 하나밖에 못들어간다.

n = 2 또는 n = 3 인 경우는 솔루션이 0개이다.

 

n = 4인 경우, 가능한 경우가 아래 그림의 가운데 두 가지 뿐이다.

그리고 이 친구들은 열 [0, 1, 2, 3] 에서 1~2 사이를 기준으로 y축 대칭이다.

따라서 이후의 모든 짝수는 첫째행 기준 n/2 열까지만 검사한 뒤 2배해주면 원하는 count를 얻을 수 있다.

n = 5 인 경우, 퀸을 놓아보면 퀸을 놓을 수 없는 자리 ( conflict 발생! ) 는 아래와 같다.

퀸은 1행부터 아래로 차곡차곡 결정되므로, 아래의 그림과 같이 변경할 수 있다.

퀸이 마지막 행에 놓일 수 있다는 말은, 모든 행에 퀸이 하나씩 자리잡았다는 말이고, 솔루션 중 하나를 완성했다는 뜻이다.

그래서 count를 1 올려준다.

퀸의 경우, 백슬래쉬 ( y = -x 그래프 ) 또는 슬래쉬 ( y = x 그래프 ) 형태의 conflict 가 발생할 수 있다. 이 경우를 걸러주기 위해, 백슬래시 또는 슬래시를 검사하는데, 이 때 사용하는 파라미터는 첫번째 인덱스이다!

( 백슬래시는 columnIndex - rowIndex, 슬래시는 rowIndex + columnIndex )

예를 들어 4 x 4 의 경우 아래의 그림과 같이 첫번째 자리 인덱스로 모든 위치를 나타낼 수 있다.

(왼쪽) 백슬래시, (오른쪽) 슬래시

첫번째 자리의 인덱스를 가지고, 어디부터 검사할 지 확인할 수 있다.

아래는 결과

 

그리고 코드

 

// Change 0 to 1 or opossite
const toggle = (board, rowIndex, columnIndex) => {
	board[rowIndex][columnIndex] = board[rowIndex][columnIndex] ? 0 : 1;
};

// is this board has any row conflict?
const hasRowConflict = (board) => {
	const n = board.length;
	for (let row = 0; row < n; row++) {
		if (board[row].filter((x) => x === 1).length > 1) {
			return true;
		}
	}
	return false;
};

// is this column has any conflict?
const isColConflict = (board, col) => {
	const n = board.length,
		result = [];
	let tmp;

	for (let row = 0; row < n; row++) {
		tmp = board[row][col];
		if (tmp) {
			result.push(tmp);
		}
		if (result.length > 1) {
			return true;
		}
	}

	return false;
};

// is this board has any column conflict?
const hasColConflict = (board) => {
	const n = board.length;
	for (let col = 0; col < n; col++) {
		if (isColConflict(board, col)) {
			return true;
		}
	}
	return false;
};

// is the slash way has any conflict?
const isSlashConflict = (board, SlashColumnIndexAtFirstRow) => {
	if (SlashColumnIndexAtFirstRow === 0) {
		return false;
	}
	const n = board.length,
		result = [];
	let tmp;

	for (let row = 0; row < n; row++) {
		tmp = board[row][SlashColumnIndexAtFirstRow - row];
		if (tmp !== undefined && tmp) {
			result.push(tmp);
		}
		if (result.length > 1) {
			return true;
		}
	}

	return false;
};

// is this board has any slash (/) conflict?
const hasSlashConflict = (board) => {
	const n = board.length;

	for (let i = 0; i < 2 * n - 1; i++) {
		if (isSlashConflict(board, i)) {
			return true;
		}
	}
	return false;
};

// is the back slash way has any conflict?
const isBackSlashConflict = (board, BackSlashColumnIndexAtFirstRow) => {
	const n = board.length;
	if (
		BackSlashColumnIndexAtFirstRow === n - 1 ||
		BackSlashColumnIndexAtFirstRow === -1 * n + 1
	) {
		return false;
	}
	const result = [];
	let tmp;

	for (let row = 0; row < n; row++) {
		tmp = board[row][BackSlashColumnIndexAtFirstRow + row];
		if (tmp !== undefined && tmp) {
			result.push(tmp);
		}
		if (result.length > 1) {
			return true;
		}
	}
	return false;
};

// is this board has any back slash (|) conflict?
const hasBackSlashConflict = (board) => {
	const n = board.length;

	for (let i = -1 * n + 1; i < n; i++) {
		if (isBackSlashConflict(board, i)) {
			return true;
		}
	}
	return false;
};

// check all confilcts for Queen
const checkConflicts = (board) => {
	return (
		hasRowConflict(board) ||
		hasColConflict(board) ||
		hasSlashConflict(board) ||
		hasBackSlashConflict(board)
	);
};

const getCountSolution = (board, n, count, rowIndex) => {
	if (rowIndex === n) {
		count++;
		return count;
	}

	for (let col = 0; col < n; col++) {
		toggle(board, rowIndex, col);
		if (!checkConflicts(board)) {
			count = getCountSolution(board, n, count, rowIndex + 1);
		}
		toggle(board, rowIndex, col);
	}
	return count;
};

const findSolution = (n, count, board) => {
	let flag = n % 2;
	let half = Math.floor(n / 2);
	for (let columnOfFirstRow = 0; columnOfFirstRow < half; columnOfFirstRow++) {
		toggle(board, 0, columnOfFirstRow);
		count = getCountSolution(board, n, count, 1);
		toggle(board, 0, columnOfFirstRow);
	}
	count *= 2;

	if (flag) {
		toggle(board, 0, half);
		count = getCountSolution(board, n, count, 1);
		toggle(board, 0, half);
	}

	return count;
};

// Create a board n*n
const createBoard = (n) => {
	const board = new Array(n);
	for (let row = 0; row < n; row++) {
		board[row] = new Array(n).fill(0);
	}

	return board;
};

const nQeens = (n) => {
	if (n === 2 || n === 3) {
		console.log(`n is ${n} and solution count is 0`);
		return;
	}

	let count = n === 0 || n === 1 ? 1 : 0;

	if (count === 0) {
		let board = createBoard(n);
		count = findSolution(n, count, board);
	}

	console.log(`n is ${n} and solution count is ${count}`);
};

const n = 13;
let start, elapsed;
for (let i = 0; i < n; i++) {
	start = new Date().getTime();
	nQeens(i);
	elapsed = new Date().getTime() - start;
	if (elapsed > 1000) {
		console.log(`running time is ${elapsed} ms`);
	}
}