[순환] N-Queens

BACK-TRACKING

 

말이 없는 판 #

말을 둔 판 *

*### 첫번째 말

##*# 두번째 말

이 경우, 세번째 말을 어느곳에도 둘 수 없으므로 두번째 말의 선택을 번복

*### 첫번째 말

###* 두번째 말

#*## 세번째 말

네번째 말 놓을 자리 없음, 세번째 말의 선택 번복

하지만 더이상 놓을 곳이 없기 때문에

두번째 말의 선택을 번복.

.

.

 

상태공간트리

찾는 해를 포함하는 트리.
상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님

되추적 기법 (Backtracking)

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

		int[] cols = new int[N+1];
		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]+")");
			else
				for(int i=1;i<N;i++) {//visit children recursively //전의 전택을 회고하라
					cols[level+1] = i; //level+1번째 말을 각각의 열에 놓기 
					if(queens(level+1)) //recursion을 호출한다 
						return true;
				}
			return false; 
		}
		
		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;
		}

 

[무료] 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 강의