[알고리즘] Recursion의 응용 : N-Queens

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

 

/*
 * Recursion의 응용 : N-Queens 6-01
 * 
 * 상태공간트리 : 찾는 해를 포함하는 트리
 * 즉, 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함
 * 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음
 * 
 * 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님
 * 
 * 
 * 되추적 기법
 * : 상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘
 */
package edu.recursion;

public class Recursion06_01 {
	// Design Recursion
	/*
	return-type queens(arguments) // arguments 매개변수 : 내가 현재 트리의 어떤 노드에 있는지를 지정
	{
		// 꽝 노드인지.
		if non-promisiong
			// 꽝 노드라면 실패 출력 or 리턴 - 문제에 따라 다름
			report failure and return;
		
		// 내가 찾고 있는 노드라면
		else if success
			// 답 출력 or 리턴
			report answer and return;
			
		// 노드에 달려있는 자식 노드를 방문
		else
			visit children recursively;
	}
	 */
	
	/*
	 *  매개변수 level은 현재 노드의 위치을 표현하고,
	 *  1번에서 level 말이 어디에 놓였는지는 전역변수 배열 cols로 표현
	 *  cols[i] = j는 i번 말이 (i행, j열)에 놓였음을 의미
	 
		 int[] cols = new int [N+1];
		 boolean queens(int level){
		 	if (!promising(level))
		 		return false;
		 	
		 	// promising 테스트를 통과했다는 가정하에 level==N이면 모든 말이 놓였다는 의미이고 성공이란 뜻!
		 	else if (level == N)
		 		return true;
		 	else
		 		visit children recursively;
		 }
	 
	 */
}

 

/*
 * Recursion의 응용 : N-Queens 6-02
 * -> false
 */
package edu.recursion;

public class Recursion06_02 {
	private static int N = 8;
	
	static int[] cols = new int [N+1];
	 static boolean queens(int level){
	 	if (!promising(level))
	 		return false;
	 	
	 	// promising 테스트를 통과했다는 가정하에 level==N이면 모든 말이 놓였다는 의미이고 성공이란 뜻!
	 	else if (level == N)
	 		return true;
	 	for (int i=1; i<=N; i++){
	 		cols[level+1] = i;
	 		// level+1번째 말을 각각의 열에 놓은 후 recursion을 호출
	 		if(queens(level+1))
	 			return true;
	 	}
	 	return false;
	 }
	 
	 /*
	  현재 level값 이전은 말들 간에는 충돌이 없음이 보장되어 있음
	  현재 level값은 마지막에 놓인 말이 이전에 놓인 다른 말들과 충돌하는지 검사하는 것으로 충분
	  */
	 // 현재까지 놓인 말들과 충돌을 했는지 안했는지 검사
	 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) {
		boolean result = queens(4);
		System.out.println(result);
	}
}