[백준/ Python] N-Queen

N-Queen

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

백트래킹

백트래킹은 모든 후보군에 대해 탐색을 하는데, 제약조건을 충족하지 않는 후보군의 경우 더이상 탐색을 진행하지 않고 이전 단계로 돌아가서(=backtrack) 다른 후보군의 탐색을 진행한다.

백트래킹 Cheat Sheet (Python)

def backtrack(candidate):
	# 만약 현재 후보군이 유효한 해라면 정답 처리하고 backtrack 함수를 종료
    if find_solution(candidate):
        output(candidate)
        return
    
    # 반복문을 돌면서 가능한 모든 후보군에 대해 탐색
    for next_candidate in list_of_candidates:
    	# 유효한 후보군인 경우에만 탐색 진행
        if is_valid(next_candidate):
            # 이 후보군을 우선 추가하고,
            place(next_candidate)
            # 후보군을 추가한 상태에서 다음 후보군에 대해서 탐색 진행
            backtrack(next_candidate)
            # 해당 후보군에 대한 탐색을 종료한 이후에는 제거
            remove(next_candidate)

백트래킹 코드

promising 조건 설계
for 문이 돌면서 첫번째 퀸을 첫번째 열부터 쭉 체크하게 된다.
예를 들어 n =4 이면 (0,0) (0,1) (0,2) (0,3) 을 체크한다.

n = int(input())

ans = 0
row = [0] * n

def is_promising(x): # x번째 행에 퀸을 놓았을 때, 그 배치가 유효한지를 판단
    for i in range(x):
        print("같은 열에 있는지", row[x] ,row[i])
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            #같은 열에 다른 퀸이 있거나 대각선상에 다른 퀸이 있는 경우 False를 반환
            #  퀸이 서로 대각선상에 위치하지 않는지를 확인하는 데 사용
            return False
    
    return True

def n_queens(x):
    global ans
    if x == n: # 탈출조건
        ans += 1
        return

    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            print(i,x)
            row[x] = i
            #x번째 행에 퀸을 i번째 열에 놓는 것
            if is_promising(x):
                n_queens(x+1)

n_queens(0)
print(ans)

참고: https://abcdefgh123123.tistory.com/330

https://leetcode.com/problems/combinations/solutions/844096/backtracking-cheatsheet-simple-solution/