[알고리즘][BackTracking] N-Queens 문제

1. N-Queens 문제란 무엇인가?

N-Queens 문제란 N x N 크기의 체스판에 N개의 퀸 기물끼리 서로 공격할 수 없도록 배치하는 경우의 수를 계산하는 문제입니다. 퀸 기물은 체스에서 가로, 세로, 대각선으로 이동할 수 있는 기물입니다. 예를 들어 N=4이라고 가정할 때 4개의 퀸이 서로를 공격할 수 없는 경우의 수는 아래와 같이 2가지 입니다.

 

2. N-Queens 접근 방법

2.1 Naive Algorithm

N-Queens 문제를 푸는 가장 직관적인 방법은 퀸을 놓을 수 있는 모든 경우의 수중에서 조건(퀸끼리 서로 공격할 수 없는)을 만족하는 경우만을 세는 방법이 있습니다. 하지만 이 방법은 N=4라고 가정할때 모든 퀸을 놓을 수 있는 경우의 수는 4*4*4*4=256 가지입니다. N이 증가하면 경우의 수는 기하급수적으로 증가할 것입니다. 이는 매우 비효율적인 방법입니다. 이러한 문제의 원인은 이미 안되는 경우에도 불구하고 모든 경우의 수를 탐색하기 때문입니다.

 

2.2 BackTracking Algorithm

백트래킹 알고리즘은 "가능한 모든 방법을 탐색한다"의 아이디어를 가집니다. 즉, 백트래킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하고 부모 노드(이전 노드)로 돌아가서 다시 탐색하는 범용적인 알고리즘입니다.

 

대표적인 완전 탐색 방법으로 DFS(Depth First Search, 깊이 우선 탐색)이 있습니다. DFS는 재귀 호출을 통하여 특정 노드의 인접 노드가 방문할 장소가 있다면 그쪽으로 이동하여 탐색하는 알고리즘입니다. 

 

정리하면 DFS를 수행하는 도중 방문한 노드가 가능성이 없는 노드라면 다시 부모 노드로 돌아가서 다른 노드를 탐색하는 방법이 백트래킹 알고리즘입니다.

 

2. BackTracking 알고리즘을 적용한 N-Queens 문제 탐색 과정

다음 그림은  N=4일때 탐색 과정 중 일부입니다. 

위의 그림과 같이 유망성이 있으면 다음 열로 이동하여 각 행마다 퀸을 두었을때 유망성이 있는지 검사합니다. 만약 4개의 행 전부 유망성이 없다면 부모 노드로 다시 돌아가서 부모 노드의 행을 다음 행으로 이동시켜 탐색합니다.

 

유망성 실패 조건

• 같은 행에 위치
• 퀸들이 대각선에 위치 ( 대각선을 판단하는 기준은 퀸들의 가로차이와 세로차이가 동일하면 대각선에 위치함)

 

3. Java언어 기반 코드 구현

public class Main2 {
	static int count = 0;
	
	/**
	 * 유망성 조건
	 * 1. 같은 행이 아님
	 * 2. 대각선이 아님 (가로 차이와 세로 차이가 같으면 대각선)
	 * 
	 * @param q 퀸들이 몇번째 행에 저장되는지 저장하는 배열
	 * @param n 유망성이 있는지 검사하는 n번째 퀸
	 * @return
	 */
	public static boolean isPromising(int[] q, int n)
	{
		for(int i = 0; i < n; i++)
		{
			// q[i]==q[n] : 같은 행
			// q[i]-q[n] : 행의 차이
			// n-i : 열의 차이
			if(q[i]==q[n] || Math.abs((q[i]-q[n]))==Math.abs(n-i))
			{
				return false;
			}	
		}
		return true;
	}
	
	public static void enumerate(int N) {
		int[] q = new int[N];	// Queen 배열, index는 열, 값은 행을 의미함
								// ex) q[0]=1, 0번째 퀸은 0번째 열에 1행에 배치
		enumerate(q, 0);
	}
	
	public static void enumerate(int[] q, int n){
		int N = q.length;
		
		// n이 끝가지 돌았다면 탐색완료이므로 count를 증가시킴
		if(n==N) 
		{
			count++;
		}
		else
		{
			for(int i = 0; i < N; i++)
			{
				q[n] = i;				// n번째 퀸을 i번째 행에 배치
				if(isPromising(q,n))	// 유망하다면 계속 탐색	
				{
					enumerate(q, n+1);
				}
			}
		}
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		enumerate(n);
		System.out.println(count);
		
	}
}

 

References

http://sooyoung32.github.io/dev/2016/03/14/n-queen-algorithm.html
https://dev-troh.tistory.com/173