[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (8퀸)

[8퀸 문제 - 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.]

※ 퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능합니다.

1. 이 문제의 정답은 92가지의 조합입니다.

2. 체스판의 가로 줄을 행, 세로 줄을 열이라 하고 배열 인덱스에 맞추어 행과 열에 0~7의 번호를 부여합니다.

3. 퀸 배치하기

1) 규칙 1 : 각 열에 퀸을 1개만 배치합니다.

2) 규칙 2 : 각 행에 퀸을 1개만 배치합니다.

4. 가지뻗기(branching)

1) 퀸의 배치를 나타내는 배열 pos를 생성합니다.

2) i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 합니다.

(1) 예를 들어, pos[0]의 값이 0이면 '0열의 퀸이 0행에 배치된 상태'를 의미합니다.

3) 이때 , pos[i]에 0부터 7까지의 값을 순서대로 대입하여 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀

메서드'입니다. 매개변수 i가 이 퀸을 배치할 열입니다. 이 메서드는 가장 먼저 main 메서드에서 set(0); 으로

호출합니다.

4) 호출된 set메서드는 매개변수 i에 0을 전달받습니다. 그리고 0 열에 1개의 퀸을 배치하는 8가지 조합을 for문에

의해 나열합니다. j 값을 0부터 7까지 1씩 증가하며 다음과 같이 재귀 호출을 합니다. set(i+1);

​

※ 이렇게 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 분할 정복법(divide and conquer)이라고 합니다. 물론 문제를 세분할 때는 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출될 수 있게 설계해야 합니다.

​

5. 분기 한정법

1) flag는 같은 행에 중복하여 퀸이 배치되는 것을 방지하기 위한 표시(flag)입니다.

2) j행에 퀸을 배치하면 flag[j] 의 값을 true로 하고, 배치되지 않은 상태의 값은 false 로 합니다.

3) 0열에 퀸을 배치하기 위해 호출한 set 메서드는 먼저 0행에 퀸을 배치합니다.(flag[0]의 값은 false입니다.)

0행에 퀸을 배치했기 때문에 flag[0]의 값을 true로 변경합니다. 그런 다음 set 메서드를 재귀적으로 호출합니다.

이렇게 호출한 set 메서드는 다음 1열에 퀸을 배치합니다.

​

※ 이처럼 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정(bounding) 조작이라 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어가는 방법을 분기 한정법(branching and bounding method) 이라고 합니다.

​

<8퀸 문제를 푸는 프로그램>

​