재귀 알고리즘 : 8퀸 문제

8퀸 문제는

8*8의 체스판에서 퀸 8개를 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제입니다.

수학자 사우스가 틀린 것으로도 유명하죠.

정답을 만족하기 위해서는 몇가지 조건을 반드시 지켜야 합니다.

1. 각 열에는 퀸을 1개만 배치한다.

2. 각 행에 퀸을 1개만 배치한다.

3. 대각선을 그엇을 때 그위에 퀸이 1개만 있도록 한다.(대각선은 총 30개입니다.)

이 조건을 만족하는 퀸의 배치 경우의 수를 구해야 합니다.

public class eightqueen{
	//가로에 퀸이 있으면 true 없으면 false 저장하는 배열 
	static boolean[] a= new boolean[8];
	//우상향 대각선에 퀸이 있으면 true 없으면 false을 저장하는 배열
	static boolean[] b= new boolean[15];
	//우하향 대각선에 퀸이 있으면 true 없으면 false을 저장하는 배열
	static boolean[] c= new boolean[15];
	
	//위치 저장하는 배열
	static int[] ind = new int[8];
	
	
	//위치를 출력하는 부분
	static void print() {
		for(int i =0;i<8;i++) {
			System.out.printf("%2d", ind[i]);
		}
		System.out.println();
	}
	
	//i는 첫열의 퀸 위치를 의미함.
	static void q8(int i) {
		for(int j=0;j<8;j++) {
			//j는 행을 의미합니다.
			//j행에 퀸이 없다면, 우상향, 우하향 대각선에 퀸이 없다면 i열의 j열에 퀸이 배치됨.
			if(a[j]==false && b[i+j]==false && c[i-j+7]==false) {
				ind[i]=j;
				//7열까지 모두 배치하고 나면 print됨.
				if(i==7) {
				print();
				}
				else {
				//i열, j행에 배치했으므로 행과 우상향 우하향 대각선 배열에 true를 넣음.
				a[j]=b[i+j]=c[i-j+7]=true;
				//다음열로 넘어가 배치를 진행함.
				q8(i+1);
				//모두 배치되었다면, false로 다시 다 바꿔줌.
				a[j]=b[i+j]=c[i-j+7]=false;
				}
			}
		}
	}
	public static void main(String[] args) {
		q8(0);
	}
}