9663: N-Queen

import sys

N = int(sys.stdin.readline())
pos = [0] * N
cnt = 0

def q(num):
    for i in range(num):
        if pos[num] == pos[i] or abs(pos[num] - pos[i]) == num - i:
            return 0
    return 1

def dfs(num):
    global cnt
    
    if num == N:
        cnt += 1
        return
    for j in range(N):
        pos[num] = j
        if q(num):
            dfs(num + 1)

dfs(0)
print(cnt)

처음엔 N*N의 False 칸을 2차 배열로 선언해주고 퀸을 놓을 때마다 True로 바꿔주며 경우의 수를 판단하려 했다. ('Do it!'책에 있던 8-Queen 방식. 문제의 N은 1 <= N <= 15)
하지만 굉장히 비효율적이고 복잡하다는 것을 깨달았다.
두 번째로 한 생각은 한번 배치를 완료하면 90°씩 회전시키거나 상하좌우로 대칭시켰을 때 동일한 형태가 나타나므로 독립된 개체만 판단하고 2, 4배 해주려 했다. 허나 이를 특정하기가 매우 어려워서 다른 방식을 택했다.
마지막으로 친구의 방식인 '백트래킹' 방식을 채용했다. 코드는 위와 같다.

한줄에 하나씩 퀸을 놓으며 대각선에 위치하는지만 판단해주었다. N개가 배치되면 cnt를 1 올려줬고, 배치할 수 없는 경우에는 이전 말을 다음 칸으로 옮기며 판단했다.
그런데 이 코드도 python3로 제출하면 시간초과가 나온다. pypy로 제출하여 겨우 통과했다.