퀸은 상, 하, 좌, 우, 대각선으로 거리제약 없이 이동할 수 있다.
N x N 체스판에 N개의 퀸을 배치해야하므로 반드시 모든 행에 퀸이 들어가야 한다.
따라서 0열부터 N-1열까지 퀸을 놓는 방법을 for문으로 돌린다. (dfs)
이전 열에 겹치는 행이 있는지 체크해준다. (check)
(x,i)
에 퀸을 놓고, 이전 행과 겹치는지 체크해준다.n
번째 행까지 이동하면, 겹치지 않게 퀸을 놓았다는 뜻이므로 cnt
를 1 증가시켜준다.import sys
input = sys.stdin.readline
def check(x):
for i in range(x):
if rows[x] == rows[i] or abs(rows[x] - rows[i]) == x - i:
return False
return True
def dfs(x):
global cnt
if x == n:
cnt += 1
else:
for i in range(n):
rows[x] = i
# (x,i)에 퀸을 놓고, 이전 행과 겹치지 않는지 체크해줌
if check(x):
# 겹치지 않으면 다음 행으로 이동
dfs(x+1)
n = int(input())
rows = [0] * n
cnt = 0
dfs(0)
print(cnt)
import sys
input = sys.stdin.readline
def check(x):
for i in range(x):
if rows[x] == rows[i] or abs(rows[x] - rows[i]) == x - i:
return False
return True
def dfs(x):
global cnt
if x == n:
cnt += 1
return
for i in range(n):
if visited[i]:
continue
rows[x] = i
if check(x):
visited[i] = True
dfs(x+1)
visited[i] = False
n = int(input())
rows = [0] * n
visited = [False] * n
cnt = 0
dfs(0)
print(cnt)