N queen 문제

n 퀸 문제는 책에 다 나와 있어서 그다지 고민하지 못했다.
그렇게 지나가기엔 심심하니까, 비트마스크를 써보면서 복습을 했다.

원래 풀이

N = int(input())

set_point = [0] * N
flag = [True] * N
flag_b = [True] * (2*N - 1)
flag_c = [True] * (2*N - 1)


def put(n, count=0):
    if n == -1:
        count += 1
    else:
        for i in range(N):
            if flag[i] and flag_b[n+i] and flag_c[n-i+N-1]:
                set_point[n] = i
                flag[i] = flag_b[i+n] = flag_c[n-i+N-1] = False
                count = put(n-1, count)
                flag[i] = flag_b[i+n] = flag_c[n-i+N-1] = True

    return count


print(put(N-1))

비트마스크를 이용한 풀이

N = int(input())

a = [0]
b = [0]
c = [0]


def nqueen(pos=0, n=N, count=[0]):
    if pos == (1 << N) - 1:
        count[0] += 1
    else:
        for i in range(N):
            if not (a[0] & (1 << i)) and not (b[0] & (1 << (n - i + N - 1))) and not (c[0] & (1 << (i + n))):
                a[0] = a[0] | (1 << i)
                b[0] = b[0] | (1 << (n - i + N-1))
                c[0] = c[0] | (1 << (i + n))
                pos = pos | (1 << n-1)
                nqueen(pos, n-1)
                a[0] = a[0] & ~(1 << i)
                b[0] = b[0] & ~(1 << (n - i + N-1))
                c[0] = c[0] & ~(1 << (i + n))

    return count[0]


print(nqueen())

비트 마스크를 이용하여 풀면 메모리나 속도에 있어 향상이 있을 줄 알았는데 되려 더 악화되었다. 이유가 무엇일까? 구현 상에 나쁜 습관이 있을 수도 있을 것 같다. 고수들의 정답을 찾아봐야겠다.