[알고리즘] 백트래킹 (backtracking) - n-Queens 문제 구현 / 파이썬 Python

4-Queens 문제 (n = 4)

4개의 퀸을 4x4 체스보드에 배치

일단, 기본 가정으로 같은 행(row)에는 놓을 수 없음

후보 해답: 4 * 4 * 4 * = 256 가지의 탐색 공간이 있음 (하나의 행에 하나만 놓을 수 있다는 것 -> 4가지, 4개의 행) -> 4*4*4*4

 

 

 

프루닝 (가지치기)와 프로미싱을 어떻게 할 것인가?

첫번째 경우 -> 2번째행 3열,4열 (퀸을 둘 수 있음)

 

두번째 행에서 3번째 열에 해당될때 모든 경우의 수가 성립하지 않으므로 다음 경우의 수로 넘어간다.

 

그다음 행에서 가능한 공간을 찾아보자.

대각선, 같은 행, 같은 열에는 존재하면 안된다. (서로 공격하지 못하는 거리에 있어야함

성립하는 경우가 없으므로 다른 경우로 넘어가자

 

N-Queens 문제 해결

• 기본 가정: 같은 행에는 퀸을 놓지 않는다
• 유망함수의 구현
  • 같은 열이나 같은 대각선에 놓이는지를 확인

 

 

유망의 조건 1: 같은 열 체크

- col[i]: i번째 행(row)에서 퀸이 놓여있는 열(column)의 위치

- col[k]: k번째 행(row)에서 퀸이 놓여있는 열(column)의 위치

- col[i] == col[k] : 같은 열에 놓이게 되므로, 유망하지 않다.

 

유망의 조건 2: 대각선 체크

col[6] - col[2] = 4 - 8 = -4

= 2 - 6 -> (열-열, 행-행 의 차이가 절댓값을 씌워준 크기와 같음)

col[6] - col[3] = 4 - 1 = 3 

= 6 - 3

 

왼쪽에서 위협하는 퀸에 대해서

• 열에서의 차이는 행에서의 차이와 같다
• col[i] - col[k] == i - k

오른쪽에서 위협하는 퀸에 대해서

• 열에서의 차이는 행에서의 차이의 마이너스 와 같다 (크기가 같다. 부호는 반대)
• col[i] - col[k] == k - i

 

col[i]와 col[k]의 절댓값으로 대각선 위협 판단

 

 

 

입력값과 출력값

def solution(n):
    col = [0] * (n + 1) # 0번째 인덱스의 값은 무시
    n_queens(col, 0)


def n_queens (col, i): 
    global answer
    n = len(col) - 1
    if (promising(col, i)): # 유망하고(규칙을 통과했다면)
        if (i == n): # 깊이의 끝까지 도달했다면
            print(col[1: n + 1]) # 출력
            answer += 1
        else:
            for j in range(1, n + 1): # 다른 상태공간을 탐색
                col[i + 1] = j
                n_queens(col, i + 1)

def promising (col, i):
    k = 1
    flag = True
    while (k < i and flag):
        if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)): # 규칙 검사
            flag = False # 규칙 중에 하나라도 틀리면 False (정답 X)
        k += 1 # 다음 상태 공간 탐색
    return flag


if __name__ == "__main__":
    answer = 0
    n = int(input())
    solution(n)
    print("가능한 경우의 수 는",answer,"가지")