[5.16] 05-3 하노이의 탑, 05-4 8퀸 문제

05-3 하노이의 탑

하노이의 탑 알아보기

def hanoi(n, st, mid, dest):
  if n == 1:
    print(f'{st} -> {dest}')
    return 
  #n-1개를 mid로 옮긴다. 

  #1개를 dest로 옮긴다. 
  hanoi(n-1, st, dest, mid)
  print(f'{st} -> {dest}')
  hanoi(n-1, mid, st, dest)

hanoi(3, 1, 2, 3)

예제 코드 -> 기둥 번호의 합으로 표현한다. 

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)

05-4 8퀸 문제 

8퀸 문제 알아보기

8퀸 문제 - 8개의 퀸이 서로 공격하여 잡을 수 없도록 8*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)

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

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)

한정 작업과 분기 한정법

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)