n = int(input()) # 체스판 크기: n × n
answer = 0
row = [0]*n # 1차원으로 좌표 표현 ex) row[1] = 2 -> (1,2)
# 동일한 열 또는 대각선에 위치한 경우, 탐색하지 않음
def is_promising(x): # x: 말을 두는 위치
for i in range(x):
# 동일한 열 또는 대각선에 위치하면
if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i): # abs(row[x]-row[i]) == abs(x-i) -> 대각선
return False # 퀸을 놓지 못함
return True # 퀸을 놓을 수 있음
def solution(x):
global answer
# n번째 칸에 닿으면 (= 탐색이 완료되면)
if x == n:
answer += 1
return
# n번째 칸에 안 닿았을 때
else:
for i in range(n):
row[x] = i # (x,i)에 퀸을 놓음
# is_promising 로직 실행
if is_promising(x):
# 재귀적으로 한칸씩 키워서 탐색 진행
solution(x+1)
solution(0)
print(answer)
