N-Queen

출처 : 백준 #9663

시간 제한	메모리 제한
10초	128MB

---

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

---

입력

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

---

출력

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

---

입출력 예시

예제 입력 1

8

예제 출력 1

92

---

풀이

• 관련 개념 : Algorithm-class-Backtracking

생각

• N-Queen 문제는 backtracking 유형의 가장 대표적인 문제이다.
• 같은 열, 같은 행, 대각선에 위치하면 안되게끔 N개의 Queen을 놓아야 한다.
• bounding function(여기서 place 함수)를 어떻게 짜느냐가 관건이다.
  • 여기서는 for문을 0부터 k-1까지 돌면서 아래 항목을 체크한다.
    • 같은 열에 위치하는지? : (board[j] == i)
    • 대각선에 위치하는지? : (abs(board[j]-i) == abs(j-k))
    • 대각선의 경우에는 기울기가 1 or -1이므로 위와 같은 식으로 계산된다.
• 본 함수인 backtrack에서는 for문을 0부터 n-1까지 돌면서 place 함수를 통과했다면, k가 도착점에 도착했는지 아닌지를 판별한 후 도착했다면 count를 1 증가 시키고 아니라면 k에 1을 더한 값을 재귀적으로 돌린다.
  

python code

# 백준 9663번 N-Queen 
from sys import stdin
input = stdin.readline
n = int(input())
board = [-1]*n

count = 0
def backtrack(board, k, n):
    global count
        
    for i in range(n):
        if place(board, k, i):
            board[k] = i
            if k == n-1:
                count += 1
                # print('chess :', end=" ")
                # for j in range(n):
                #     print(board[j], end=" ")
                # print()
                return
            else:
                backtrack(board, k+1, n)
            

def place(board, k, i):
    for j in range(k):
        if (board[j] == i) or (abs(board[j]-i) == abs(j-k)):
            return False
    return True


backtrack(board, 0, n)
print(count)