[C++] UVa 750 : 8 Queens Chess Problem

8x8 체스판에 퀸 8개를 서로 공격할 수 없도록 하는 모든 배치를 구한다. 각 배치는 사전식 순서대로 출력

좌표(a,b) - a번째 row, b번재 column에는 반드시 queen이 위치해야한다.

 

#input

TC개수와 퀸을 반드시 배치해야하는 좌표

 

 

# SearchSpace를 줄이는 게 관건이므로 불필요한 search를 하지 않기 위해 신경써야 한다.

1.  64개의 칸에 가능한 8개의 을 모두 배치
   • == ~40억개의 경우의수
2. 하나의 퀸이 하나의 column에만 들어갈 수 있다는 사실을 이용하기.
   • == 8**8~1700만 개의 경우의 수
3.  같은 row에도 두개의 퀸이 존재할 수 없다는 사실을 이용
   • 퀸이(j,i)에 있는 경우 row[i]=j라고 할 때, Row array는 permutation이 될 수 밖에 없으므로 이 경우 총 탐색 공간의 크기는 8! ~ 40000으로 줄어든다.
4. 3에서 불가능한 조건을 좀더 생각
   • 위치 (i,j)와 (a,b)에 두 퀸이 있을 때 |i-j| = |a-b|인 경우 두 퀸은 같이 존재할 수 없다
     • 8개의 퀸은 겹치는 좌표값이 존재하면 문제의 조건을 성립할 수 없다. 때문에 위의 조건을 만족해야 8개의 퀸을 공격할 수 없도록 배치 가능하다.
   • 위의 제약조건을 만족하는 값들 중에서 row[b]=a인 값들을 출력한다.

 

#include <iostream>
#

int row[8], TC, a, b, lineCounter;

/*
* row : Queen이 어디에 배치되었는지 저장하는 배열
*  => row[c] : c열에 배치된 queen의 행 좌표를 저장
* TC: 입력받는 case의 수 
  lineCounter: solution의 수 
*/
bool place(int r, int c) {
	//이전 장소를 체크한다
	for (int prev = 0; prev < c; prev++) { // 모든 (row[prev],prev)에 대해 확인한다.

		if (row[prev] == r || (abs(row[prev] - r) == abs(prev - c)))  
			//row[prev] : prev열에 배치 된 Queen의 행좌표  | prev-c : column좌표 상 차이
			return false; 
		/*
		* 같은 행에 있거나 같은 대각선 상에 있는 경우 배치 불가
		  # 같은 열에 있는 Queen을 확인하지 않는 이유 : 
		  	같은 열에 있는 퀸을 확인하게 된다면, 재귀적 수행에서 같은 열에 배치된 지난 case를 보게 된다. 
            	=>재귀적 수행이 불가하게됨.
		  # 모든 열에 대해 살펴보지 않는 이유 :
		 	 모든 열에 대해 살펴본다면 재귀적 수행이 불가능.
		  	 => 왜냐면 한 번 possible한 케이스가 정해진 후 다른 possible한 케이스를 구하는 과정에서 
          		모든 열을 검사하게 된다면, 지난 case의 배치를 보게 된다.

		*/		return true;
	}
}
void backtrack(int c) {
	if (c == 8) {
		printf("%2d    ", ++lineCounter);
		for (int j = 0; j < 8; j++) {
			printf("%d", row[j] + 1);
		}
		printf("\n");
	}
	for (int r = 0; r < 8; r++) // try all possible row( ; ; ) // y p
		if (place(r, c)) { // if can place a queen at this col and row
			row[c] = r; 
			if (r == a && row[b] != a) break;
			backtrack(c + 1); // put this queen here and recurse
		}
}
int main() {
	scanf("%d", &TC);
	while (TC--) {
		scanf("%d %d", &a, &b);	
		--a; 
		--b;	//index가 0부터 시작하도록 변경한다.
		memset(row, 0, sizeof(row));
		lineCounter = 0;	//solution의 개수 표시
		printf("SOLN       COLUMN\n");
		printf(" #      1 2 3 4 5 6 7 8\n\n");
		backtrack(0);	//가능한 모든 8!개의 후보해를 생성한다.
		if (TC) printf("\n");	//blank between each case
	}

	return 0;
}

 

column애 대한 재귀적 수행으로 작동된다.

backtrack() 함수가 재귀적 수행을 핵심적으로 담당하는 알고리즘.

하나의 체스 판을 모두 채운다 == row배열을 모두 채운다.

 

backtrack()

채워야할 column이 주어진 경우 column 0~c-1 까지 어떤 말들이 채워져 있다는 사실을 고려하여 해당 열 C에서 퀸을 배치할 수 있는 모든 행 row를 찾아서 퀸을 배치한 후 다음 열로 넘어간다.

# 현재 열 C에서 배치할 수 있는 row가 없을 경우

=> 불가능한 case. 아무 동작도 실행하지 않는다.  => 해당 케이스는 버려짐

이러한 방법으로 모든 column들이 가득 차면 가능한 case가 완성 된 것이다. 

 

 

 

아 ㄹㅇ 1도 모르겠다 이게 뭐냐.

 

이해하고 다시 돌아온다.

 

 

참고 url : https://hezma.tistory.com/50