[알고리즘] Backtracking | n Queens Problem

Backtracking Technique

- dead end를 만나면 뒤로 돌아가서 다른 선택지를 선택함

- Depth First Search(DFS | 깊이 우선 탐색)으로 진행

a modified depth-first-search of a tree (수정된 깊이 우선 탐색)

: dead end라는걸 알고 있다면 그 노드는 탐색하지 않음 //유망함수로 판별

promising function(유망 함수)

특정 상태에서 이어진 경로가 해결책이 될 가능성이 있는지 결정 -> 문제의 해결 가능성을 평가하기 위함.

 

-> 트리를 탐색하며 유망함수를 통해 유망한 트리만 탐색함.

The Depth First Search(깊이 우선 탐색) //일반적인 방법

1. 루트 방문

2. 하위 노드 방문(왼쪽 -> 오른쪽)

//The Depth-First Search

void depth_first_tree_search(node v){
	node u;
    visit v; //v를 확인
    for (each child u of v)
    	depth_first_tree_Search(u) //자식 노드 확인

 

The General Backtracking Algorithm

void checknode (node v) {
	node u; //자식노드
    if(promising(v)) //유망한 값이 있다면
    	if(there is a solution at v) //v가 해결책이라면
        	write the solution;
        else
        	for(each child u of v) //아니라면 자식노드(u) 탐색
            	checknode(u);

The Revised Backtracking Algorithm

void expand(node v) {
	node u;
    
    for(each child u of v) //v의 모든 노드 확인
    	if(promising(u)) //promising하고
        	if(there is a solution at u) //u가 solution이라면
            	write the solution; //그대로 출력
            else
            	expand(u); //아니라면 다시 expand하기
}

4 Queens Problem

- 4 x 4 체스보드에서 Queen이 서로를 위협하지 않게 배치

 

- Queen들은 같은 열에 있을 수 없음

- Queen들은 같은 줄에 있을 수 없음

- Queen들은 같은 대각선에 있을 수 없음

 

 

The state space tree for the 4-Queens problem

4 Queens Problem(again)

전체 노드의 수(트리의 크기)

1 : 루트노드

4 : 그 밑에 4개의 노드

4^2 : 4개의 노드가 4개씩 자식 노드를 갖고 있음

case1. 시작노드에서 각 리프노드까지의 경우의 수 : 4^4 = 256

case2. DFS 방식으로 방문했을 때 : 155

case3. promising function을 사용할 경우 : 27

n Queens Problem

전체 노드의 수(트리의 크기)

4Queens Problem과 동일한 방식

< 등비수열 합 공식에 의해 이만큼의 노드를 갖게 됨

 

The promising function

: 대각선으로 잡아먹히는 경우

 

각 Queen의 가로 좌표의 차와 세로 좌표의 차가 동일한 경우 두 Queen은 대각선에 존재한다.

ex1. | 2 - 6 | == | 8 - 4 | => 대각선에 존재

ex2. | 1 - 4 | == | 3 - 6 | => 대각선에 존재

 

 

Upper bound of the number of promising nodes

- 8 * 8 체스판 : 1 + 8 + 8 * 7 + 8 * 7 * 6 + ... + 8! = 109,601

- 일반적인 경우 : 1 + n + n(n - 1) + n(n - 1)(n - 2) + ... + n!

- 첫번째 퀸이 갈 수 있는 경우 : n개

- 2번째 퀸이 갈 수 있는 경우 n - 1개(n과 같은 라인에 존재할 수 없음) => n(n-1)

...

아무튼 promising function을 디테일하게 디자인하면 할수록 더 효율적이다~