Back Tracking(백트래킹)

개념

• 백트레킹은 한정 조건을 가진 문제를 풀려는 전략이다.
• 백트레킹은 기본적으로 완전 탐색을 하는 것을 기반으로 한다.
• 즉, 가능한 모든 경우를 고려하는 것이 첫 번째다. 그리고 각각의 경우의 수를 만족하기 위한 한정적인 조건들이 존재한다.
• 가능성이 있는 후보를 점진적으로 구축하고 후보가 특정 목표까지 완료될 수 없다고 판단하는 즉시 후보를 포기한다."
• 이 때 후보군을 포기할 때 솔루션에 영향을 주는 부분을 변경했다면, 그 것을 반드시 원복해야한다.
• 이 것은 백트레킹뿐 아니라 완전 탐색에도 동일하게 원복시켜줘야 한다.
• 가지치기라고 생각하면 편하다.

N퀸 강의 보고 정리하기

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

[9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net](https://www.acmicpc.net/problem/9663)

• 8-Queens(n=8) 문제의 일반화된 문제
• n x n 체스보드에 n개의 퀸을 배치하는 문제
  • 어떤 퀸도 다른 퀸에 의해서 잡아먹히지 않도록 배치해야 함
  • 즉, 같은 행, 열, 대각선에는 다른 퀸을 놓을 수 없음
• n-Queens 문제: 백트래킹
  • 백트래킹으로 문제 해결:
    • 임의의 집합에서 기준에 따라 원소의 순서를 선택
• n-queens문제에 적용
  • 임의의 집합(set): 체스보드에 있는 n^2개의 가능한 위치
  • 기준(criterion): 새로 놓을 퀸이 다른 퀸을 위협할 수 없음
  • 원소의 순서(sequence): 퀸을 놓을 수 있는 n개의 위치

# baekjoon 3344 N-Queen 백트레킹
# 8x8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제
# 퀸은 같은 행,열,대각선의 말들을 공격할 수 있다.
# N-Queen은 파이썬으로는 baekjoon 3344에서는 시간초과가 난다.

n = int(input())
col = [0] * (n + 1)
cnt = 0

# parameter i: Depth
#           col: 칼럼 번호
def n_queen(i, col):
    global cnt
    # n은 column의 길이 빼기 1
    # 이유는 0 부터 시작하기 때문
    n = len(col) - 1
    # i 번째 댑스의 column을 가지고 promising 한지 확인
    if (promising(i, col)):
        # 만약 i와 n이 같다면 => 내가 모든 퀸을 프로미싱한 곳에 다 놓았다
        if (i == n):
            cnt += 1
            # 1번 칼럼부터 끝까지 출력
            print(col[1: n + 1])
        else:
            # 그렇지 않으면 다음 댑스의 1번 칼럼부터 끝까지 탐색
            for j in range(1, n + 1):
                # 1,2,3,4 ...n 번째에 퀸을 놔본다.
                col[i + 1] = j
                # 재귀 호출
                n_queen(i + 1, col)

# parameter i: Depth
#           col: 칼럼 번호
def promising(i, col):
    k = 1
    flag = True
    while (k < i and flag):
        # col[i] == col[k]의 의미는 같은 열에 있는지 체크하는 것이다.
        # abs(col[i] - col[k]) == (i - k) 대각선에 있는지 체크
        if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)):
            # 퀸에게 위협 당한다면 False 처리
            flag = False
        # 인덱스를 증가시킨다.
        k += 1
    return flag

n_queen(0,col)
print(cnt)