N-Queens 여왕 알고리즘 with JAVA

  점점 공부하면서 어려워지는 알고리즘을 배우고 있는 것 같다는 생각이 든다. 재귀적인 함수 사고를 가져가고 있다고 생각했는데, 이번에는 게임(?)에 실제로 사용될 법한 알고리즘을 공부해 보았다. 여왕 알고리즘은 사이즈가 N인 정사각형 2차원 배열에 N만큼의 여왕이 있어야 하는데, 서로의 영향권에 들지 않는 곳에만 있어야 한다. 이게 무슨 말이냐면, 다음과 같이 여왕들이 서로의 간섭을 피하기 위해서는 나름의 규칙이 존재한다는 것이다.

 

• 여왕이 놓인 위치를 기준으로 가로, 세로, 좌우의 대각선으로는 다른 여왕이 놓일 수 없다.
• 아래의 사진을 참고하자면, 점선이 지나는 곳이 놓인 여왕의 영향권에 드는 구역이다.
• 따라서 여왕의 영향권에 들지 않는 구역에만 또 다른 여왕을 배치할 수 있다.

여기서 잠깐!

프로그래밍을 할 때 여기서 굳이 무겁게 생각하지 않아도 될 부분은 바로 가로의 영역이다.

행우선으로 순회하는 경우에는 1번째 행에 여왕을 놓았다면 굳이 같은 행의 다음 열을 검사하지 않아도 된다.

 

문제 확인

---

크기가 N인 행렬이 있다면, 위의 규칙에 따라 여왕을 최대로 놓을 수 있는 경우의 수인 N의 상황을 만들려고 한다.

N-Queens(여왕) 알고리즘을 코딩하시오.

 

코드

---

public class NQueens {

	int size=0;
	int cols[];
	
	NQueens(int size) {
		this.size = size;
		cols= new int[size+1];
	}
	
	NQueens() {
		this(4);
	}
	
	boolean queens() {
		return queens(0);
	}
	
	boolean queens(int level) {//행렬의 크기에 따라 여왕을 하나씩 놓는 시나리오를 구상한다.
		if(promising(level)==false) {//여왕이 놓일 수 있는 위치인지 확인하고 거짓이면 거짓을 반환한다.
			return false;
		} else if(level==size) { // Recursive Case가 존재해야 한다.
			for(int i=0;i<=size;i++) {				
				System.out.format("최종: (%d, %d)\n",i, cols[i]);
			}
			return true;
		}		
		//현재 놓인 말 다음에 놓일 말을 하나씩 대입하면서 시나리오를 그려 본다. 
		for(int i=1;i<=size;i++) {
			cols[level+1]=i;
			System.out.format("\n\n(%d, %d)에 여왕을 놓아 보겠다!\n", level+1,i);
			boolean isAvailable = queens(level+1);
			System.out.format("이 자리는 다른 여왕의 영향권에 들지 않는 자리인가? %b (예:T,아니오:F)\n",isAvailable);
			if(isAvailable) {
				return true;
			}
		}		
		return false;
	}
	
	boolean promising(int level) {//여왕이 놓일 수 있는 위치인지 확인하기
		/*
		1. 같은 열에 존재하는지 판별하기
		2. 이미 놓인 여왕의 대각선의 위치에 놓였는지 판별하기
		1, 2의 케이스의 경우 return false를 반환한다. 
		*/
		System.out.format("level =%d \n",level);
		for(int i=0;i<level;i++) {//0레벨부터 현재 level의 직전까지만 비교하면 됨. level level 자기 자신을 비교할 필요가 없음.
			System.out.format("검사할 여왕 (%d,%d)에 있음 => cols[i]=%d, cols[level]=%d \n",i,cols[i], cols[i], cols[level]);
			if(cols[i]==cols[level]) {
				System.out.format("%d==%d 이므로 false 반환\n", cols[i], cols[level]);
				return false;
			}else if(level-i==Math.abs(cols[level]-cols[i])) {
				System.out.format("%d-%d==|%d-%d| 이므로 false 반환\n", level, i, cols[level], cols[i] );
				return false;
			}
		}
		//지금까지 놓인 여왕을 비교했을 때 아무런 제약이 없었다면 return true를 반환한다.
		System.out.println("아무런 제약사항이 없는 자리이므로 True 반환");
		return true;
	}
	
	public static void main(String[] args) {
		NQueens n = new NQueens(8);
		n.queens();
	}
}

 

해설 (크기가 4인 경우)

---

컴퓨터 입장에서는 깊이우선 탐색이라는 개념이 필요하다.

  깊이우선 탐색은 스택의 성질과 같으므로 FIFO 방식으로 탐색을 하게 된다. 조건에 부합하면 계속해서 아래의 깊이로 파고 드는 거고, 거기서 조건에 맞지 않다면 다시 상위 단계로 나와서 다른 시나리오로 파고 들어간다고 생각하면 된다. 글로서는 온전히 설명할 수 없으니 아래의 트리 구조 그림으로 대체한다. 아래의 트리는 탐색할 수 있는 모든 경우의 수이다. 아래의 그림에서 적힌 모두의 경우를 탐색하는 것이 아니라 조건에 하나라도 맞지 않으면 상위 단계로 올라가야 하며, 조건이 모두 맞은 경우 완수한 것이므로 나머지 경우의 수는 탐색하지 않는다. (ex: 1-1: 레벨1에서 열 1번째)

  다음은 모든 경우의 수에서 탐색이 성공한 경우의 수만 추려본 것이다.

디버깅

---

---

 

이번 알고리즘은 확실히 난도가 있는 것 같다. 어렵다.