[Algorithm] 재귀 알고리즘_4(8퀸 문제)

05-4 8퀸 문제

8퀸 문제 알아보기

8퀸 문제(8-Queen prooblem)는 재귀 알고리즘을 설명할 때 자주 나오는 예제입니다.

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

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

실습 5-7 각 열에 퀸을 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)

이렇게 차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법을 분기(branching) 작업이라고 합니다. 하노이의 탑이나 8퀸 문제처럼 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법을 분할 정복법(divide and conquer 분할 해결법)이라고 합니다.

한정 작업과 분기 한정법

실습 5-8 행과 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기

# 행과 열에 퀸을 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)

실습 5-8 프로그램은 flag라는 새로운 list형 배열을 사용합니다. 이 배열은 같은 행에 중복하여 퀸을 배치하지 않기 위한 표시로 사용됩니다.

8퀸 문제 해결 프로그램 만들기

실습 5-9 8퀸 문제 알고리즘 구현하기

# 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)                              # 0열에 퀸을 배치

# 8퀸 문제 알고리즘 □와 ■로 구현하기

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

def put() -> None:
  """퀸의 배치를 □와 ■로 출력"""
  for j in range(8):
    for i 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)                              # 0열에 퀸을 배치

 

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%9E%AC%EA%B7%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습