Recursion 응용 : N-Queens Problem

1. N - Queens Problem ( 8 - Queens Problem )

어떠한 행, 열, 대각선에 말이 겹치지 않도록 놓는 방법

  

1) 상태공간트리(State-Space Tree)

상태공간트리란 찾는해를 포함하는 트리를 말한다. 즉 해가 존재한다면 그것은 반드시 이 트리의 어떠 한 노드에 해당한다.

→ 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아니다.

2) 되추적 기법(Backtracking)

상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다.

[출처: https://ko.wikipedia.org]

2. Design Recursion

1) 전체 pseudocode 

int [ ] cols = new int [N+1];

return-type(boolean) queens( arguments = int level ){

if non-promising 

report failure and return;

else if success (level == N) // level==N이면 모든말이 놓였다는 의미이고 따라서 성공이다.

report answer and return;

else

visit children recursively;  // level + 1 번째 말을 각각의 열에 높은 후 recursion을 호출한다.

}

2) promising Test pseudocode

boolean promising(int level){

for(int i=1; i<level; i++){

if(cols[i]==cols[level]) // 같은 열에 놓여있는지 검사

return false;

else if on the same diagonal  //같은 대각선에 놓였는지 검사 

  // level - i = | cols[level]-cols[i] |

return false;

}

return true;

}

3. 소스 코드

 

public class NQueensProblem {
	
	public static final int N = 8;
	public static int[] cols = new int[N+1];
		
	public static boolean queens(int level){
		if(!promising(level))
			return false;
		else if(level==N){
			for(int i=1; i<=N; i++)
				System.out.println("("+i+", "+cols[i]+")");
			return true;
		}
			
		for(int i=1; i<=N; i++){
			cols[level+1] = i;
			if(queens(level+1))
				return true;
		}
		return false;
	}
	public static boolean promising(int level){
		for(int i=1; i<level; i++){
			if(cols[i]==cols[level])
				return false;
			else if(level-i==Math.abs(cols[level]-cols[i]))
				return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		queens(0);
	}
}