13. 하노이의 탑과 8 Queens

---

 

 

1. 하노이의 탑 (Towers of Hanoi)

1883년 프랑수아 E. A. 뤼카가 개발한 게임 퍼즐.

기둥 3개를 이용해서 원반을 옮겨 쌓은 문제로, 규칙은 다음과 같다.

• 1번째 기둥에 크기가 모두 다른 원반이 크기 순으로 쌓여 있다.
• 원반은 1개씩 옮겨 쌓을 수 있다.
• 큰 원반은 작은 원반 위에 쌓을 수 없다.

 

1.1) 원반이 3개일 경우

원반 1과 원반 2를 그룹으로 묶어서 중간 기둥으로 이동시킨다.

원반 3을 목표 기둥으로 이동시킨다.

그룹(원반 1, 2)을 목표 기둥으로 이동시킨다.

 

1.2) 원반이 2개인 경우

원반 1을 중간 기둥으로 이동시킨다.

원반 2를 목표 기둥으로 이동시킨다.

원반 1을 목표 기둥으로 이동시킨다.

 

1.3) 원반이 4개인 경우

원반 1, 2, 3을 그룹으로 묶어 중간 기둥으로 이동시킨다.

원반 4를 목표 기둥으로 이동시킨다.

그룹(원반 1, 2, 3)을 목표 기둥으로 이동시킨다.

 

1.4) 원반이 n개인 경우

바닥에 있는 원반을 제외한 그룹을 시작 기둥에서 중간 기둥으로 이동시킨다.

바닥에 있는 원반을 목표 기둥으로 이동시킨다.

바닥에 있는 원반을 제외한 그룹 중간 기둥에서 목표 기둥으로 이동시킨다.

1, 3 단계는 재귀적으로 수행된다.

 

1.5) 하노이의 탑 구현하기

def move(no: int, x: int, y: int) -> None :
    if (no > 1) :
        move(no-1, x, 6-x-y)
        
    print(f"원반 {no}: {x} -> {y}")
    
    if (no > 1) :
        move(no-1, 6-x-y, y)
    
    
print("하노이의 탑")

n = int(input("원반 개수: "))

move(n, 1, 3)

 

---

 

2. 분할 정복법 (Divide and Conquer)

큰 문제를 작은 문제로 분할, 작은 문제 풀이의 결합으로 전체 풀이를 얻는 방법이다.

작은 문제 풀이법으로 큰 문제 풀이법을 도출할 수 있도록 설계해야 한다.

분할 해결법이라고도 부른다.

 

---

 

3. 8 퀸즈 문제 (8-Queens Problem)

8개의 퀸이 서로를 공격해 잡을 수 없도록 8*8 크기의 체스판에 배치하는 문제

총 92개의 해답이 존재한다.

 

3.1) 퀸 배치하기

체스판의 크기는 64칸이다. (8 * 8)

1번째 퀸을 배치할 때는 64칸 중 1칸을 선택한다.

2번째 퀸을 배치할 때는 63칸 중 1칸을 선택한다.

64 * 63 * ~ * 57 = 178,462,987,637,760 가짓수

 

3.2) 규칙 1

각 열에는 퀸을 1개만 배치 가능하다.

8^8 = 16,777,216 가짓수

 

3.3) 규칙 2

각 행에는 퀸을 1개만 배치 가능하다.

규칙 1, 2를 동시에 적용할 경우, 8! = 40,320 가짓수가 나온다.

 

3.4) 각 열에 퀸을 1개만 배치하는 문제

분할 정복법을 적용해 8 퀸즈 문제를 해결해보자.

모든 열에 물음표가 있고, 물음표에 퀸을 채우면서 배치한다.

 

3.5) 0열에서 퀸을 배치하는 방법

원래 문제를 8개의 문제로 전환한다.

여기에는 총 8가지의 방법이 존재한다.

 

3.6) 1열에서 퀸을 배치하는 방법

다시 8개의 문제로 전환하자.

0열과 1열에 퀸을 배치하는 방법은 총 64가지이다.

 

3.7) 8개의 퀸 배치 조합

16,777,216가지의 경우의 수가 나온다.

 

3.8) 분기: 모든 퀸 배치 조합 나열하기

pos = [0] * 8

def put() -> None :
    for i in range(8) :
        print(f"{pos[i]:2}", end='')
    print()
    
    
def set(i: int) -> None :
    for j in range(8) :
        pos[i] = j
        
        if (i == 7) :
            put()
        else :
            set(i + 1)
set(0)

 

3.9) 분기한정법: 규칙 2 적용

pos = [0] * 8
flag = [False] * 8

def put() -> None :
    for i in range(8) :
        print(f"{pos[i]:2}", end='')
    print()
    
    
def set(i: int) -> None :
    for j in range(8) :
        if not (flag[j]) :
            pos[i] = j
        
            if (i == 7) : 
                put()
            else :
                flag[j] = True
                set(i + 1)
                flag[j] = False
set(0)

 

3.10) 분기한정법: 8 퀸즈 문제 해답

pos = [0] * 8
flag_a = [False] * 8
flag_b = [False] * 15
flag_c = [False] * 15

def put() -> None :
    for i in range(8) :
        print(f"{pos[i]:2}", end='')
    print()
    
    
def set(i: int) -> None :
    for j in range(8) :
        if not (flag_a[j] and not flag_b[i+j] and not flag_c[i-j+7]) :
            pos[i] = j
        
            if (i == 7) : 
                put()
            else :
                flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = True
                set(i + 1)
                flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = False
set(0)

 

---

 

4. 분기, 한정, 분기한정법이란?

위에서 8 퀸즈 문제를 해결하는 과정에서 언급된 분기 작업, 한정 작업, 분기한정법의 용어 정의를 살펴본다.

• 분기 작업 (Branching): 차례대로 가지가 뻗어 나가듯이 문제를 나누는 작업
• 한정 작업 (Bounding): 불필요한 조합을 열거하지 않기 위해 필요하지 않은 분기를 지우는 작업
• 분기한정법 (Branch and Bounding Method): 분기 작업 + 한정 작업

 

---

 

---

수고하셨습니다!

---