하노이의 탑, 8퀸문제(재귀함수 응용)

하노이의 탑

출처: Do it!자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편

재귀함수를 이용해 하노이의 탑을 구현해본다.

https://velog.io/@jimmy48/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98-%ED%83%91

기둥이 세개 있고, 원반이 3개 있을때,

1번 2번 원반을 중간기둥으로 옮기고, 3번 원반을 목표기둥으로 옮긴후 1&2번 원반을 3번 원반이 있는 목표 기둥 위에 쌓아 올린다.

def move(no:int,x:int,y:int)->None:
  #원반 no개를 x기둥에서 y기둥으로 옮김
  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)

하노이의 탑을 구현합니다 원반의 개수를 입력하세요 : 3

원반[1]를 1기둥에서 3기둥을 옮깁니다

원반[2]를 1기둥에서 2기둥을 옮깁니다

원반[1]를 3기둥에서 2기둥을 옮깁니다

원반[3]를 1기둥에서 3기둥을 옮깁니다

원반[1]를 2기둥에서 1기둥을 옮깁니다

원반[2]를 2기둥에서 3기둥을 옮깁니다

원반[1]를 1기둥에서 3기둥을 옮깁니다

 

n = 3이라고 가정했을때, 

move(3,1,3) 
	move(2,1,2):
    		move(1,1,3) -> 1) 원반 1을 1기둥-> 3기둥
        			   2) 원반 2를 1기둥 -> 2기둥
        
       		 move(1,3,2) -> 3)원반 1를 3기둥 -> 2기둥
    					4)원반 3을 1기둥 -> 3기둥
    move(2,2,3)
    		move(1,2,1) 5) 원반 1을 2기둥 -> 1기둥
        			6) 원반 2를 2기둥 -> 3기둥
        
       		 move(1,1,3) 7) 원반 1을 1기둥 -> 3기둥

기둥 번호의 합이 6(1+2+3) 이므로 목표기둥이 어느위치에 있든 6-x-y로 나타낸다. 

재귀 알고리즘

8퀸 문제는 다음과 같다. 

 

8개의 퀸이 서로 공격하여 잡을 수 없도록 8x8 체스판에 배치하세요

 

위의 문제에 대한 결과는 92가지 해결방법이 나온다. 

 

백준에도 n-퀸 문제라고 8이아닌 정해져있지 않은 n으로 체스문제의 경우의 수를 푸는 문제가 있다.

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

https://velog.io/@jimmy48/8%ED%80%B8-%EB%AC%B8%EC%A0%9C

퀸 배치에는 다음과 같은 규칙을 성립한다.

규칙 1) 각 열에 퀸을 1개만 배치한다.

규칙 1을 적용하면 8^8 = 16,777,216 개가 나온다. 여전히 많으므로 줄여야 한다. 

 

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

https://velog.io/@from-minju/c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-8%ED%80%B8-%EB%AC%B8%EC%A0%9C

이런방식으로 하면 조합의 개수는 줄어들지만 이러한 조합의 알괴즘은 간단히 만들 수 없다. 

분기 작업으로 문제 해결하기

i열에 배치한 퀸의 위치가 j행이면 pos[i]의 값을 j로 한다. 

이때 set()은 pos[i]에 0~7값을 차례로 대입하여 i열에 퀸을 한개만 배치하는 8가지 조합을 만든다. 

set(0)

호출된 set() 함수는 i에 0을 전달받는다. 0열에 퀸을 1개만 배치한다. 여기서 0열의 배치가 확정되므로 다음 1열의 배치가 필요하다. 

set(i+1)

이 호출을 통해 0열에서 했던 작업을 다음열인 1열에서 수행한다.

#각 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열
pos = [0]*8 #각 열에서 퀸의 위치를 출력
def put()->None:
  #각열에 배치한 퀸의 위치를 출력
  for i in range(8):
    print(f'{pos[i]:2}',end='')
  print()
def set(i:int)-> None:
  #i열에 퀸을 배치
  for j in range(8):
    pos[i]=j #퀸을 j행에 배치
    if i == 7: #모든열에 퀸 배치를 종료
      put() # 퀸 위치 출력
    else:
      set(i+1) # 다음열에 퀸 배치

set(0) #0열에 퀸을 배치

i가 7이 되면 퀸 8개의 배치 작업이 끝난다. 이런식으로 차례대로 가지가 뻗어나가듯이 조합을 열거하는 방법을 분기작업이라고 한다. 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법을 분할 정복법이라고 한다. 

한정 작업과 분기 한정법

위에선 규칙2(각 행에 퀸 1개 배치)를 적용하지 않은 코드이다. 여기선 규칙2를 적용해보았다. 

행과 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열해보았다

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:
  #i열에 알맞은 위치에 퀸을 배치
  for j in range(8):
    if not flag[j]: #j행에 퀸을 배치하지 않았으면
      pos[i]=j #퀸을 j행에 배치 
      if i == 7: #모든 열에 퀸 배치를 완료
        put()
      else:
        flag[j]=True
        set(i+1) #다음열에 퀸 배치
        flag[j]=False


set(0)

flag는 새로운 list 배열을 사용한다. 같은 행에 중복하여 퀸을 배치하지 않기 위한 표시로 사용된다. j행에 퀸을 배치하면 flag[j]를 True,  배치 하지 않으면 False로 한다. 

https://velog.io/@from-minju/c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-8%ED%80%B8-%EB%AC%B8%EC%A0%9C

0행, flag[0]은 이미 True 이므로 set () 함수를 재귀 호출 하지 않는다. 

1행, flag[1]은 이미 False이므로 아직 퀸을 배치 하지 않았다. if 재귀행을 실행하고 set() 함수를 재귀 호출하여 다음열인 2열에 퀸을 배치한다. 

set(i+1) 함수가 끝나면 퀸을 j행에서 제거해야하기 때문에 flag[j]= False를 대입한다. flag 배열은 각 행에 퀸이 이미 배치되었는지를 나타낸다. 퀸을 배치할 때 해당 행을 사용 중임을 나타내기 위해 True로 설정하고, 다음 열에 퀸을 배치하기 위해 다시 재귀 호출한다. 재귀 호출이 끝나고 돌아오면, 현재 행에서 퀸을 제거하고 다른 위치에 퀸을 배치할 가능성을 탐색해야 한다. flag[j] = False로 설정하여 현재 행이 다시 사용 가능함을 나타낸다. set함수에서는 퀸을 아직 배치하지 않은 행(flag가 False)인 행에만 퀸을 배치할 수 있다. 

필요 하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법을 한정(bounding) 작업이라고 한다.

 

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:
  #i열에 알맞은 위치에 퀸을 배치
  for j in range(8):
    if ( not flag_a[j] #j행에 퀸이 배치되지 않았다면
        and not flag_b[i+j] #대각선뱡향으로 퀸이 배치되지 않았다면 ↙↗
         and not flag_c[i-j+7]):#대각선뱡향으로 퀸이 배치되지 않았다면 ↘↖
      pos[i] = j # 퀸을 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)

https://velog.io/@from-minju/c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-8%ED%80%B8-%EB%AC%B8%EC%A0%9C

배치된 퀸을 검토할때 점선처럼 대각선으로 배치되었는지 판단한다. 대각선 방향 어느곳인가 퀸을 배치했다면 다른칸에는 더이상 배치하지 않는다. 

flag_c[7]이 True이므로 이미 0열 0행에 퀸이 배치되었기 떄문에 1열1행에 퀸을 배치하지 않는다.

pos = [0]*8 #각 열에서 퀸의 위치
flag_a = [False]*8 #각 행에 퀸을 배치했는지 체크
flag_b = [False]*15 #대각선 뱡향으로 퀸을 배치했는지 체크 ↙↗
flag_c = [False]*15#대각선 뱡향으로 퀸을 배치했는지 체크 ↘↖

def put()->None:
  #각열에 배치한 퀸의 위치를 출력
  for i in range(8):
    for j in range(8):
      print('■'if pos[i]==j else '□',end='')
    print()
  print()

def set(i:int)-> None:
  #i열에 알맞은 위치에 퀸을 배치
  for j in range(8):
    if ( not flag_a[j] #j행에 퀸이 배치되지 않았다면
        and not flag_b[i+j] #대각선뱡향으로 퀸이 배치되지 않았다면 ↙↗
         and not flag_c[i-j+7]):#대각선뱡향으로 퀸이 배치되지 않았다면 ↘↖
      pos[i] = j # 퀸을 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)