N-퀸 배치 계산기

92가지입니다. 다만 판을 돌리거나 뒤집어 겹치는 것을 하나로 세면 12가지로 줄어듭니다. 회전 네 가지와 각각의 거울상까지 여덟 가지 대칭이 있어 대표 하나가 최대 여덟 개를 묶는데, 92 ÷ 12가 정확히 8이 아닌 것은 자기 자신과 겹치는 대칭적인 배치가 있기 때문입니다.

N = 2와 3뿐입니다. 2×2는 한 개를 놓는 순간 남은 세 칸이 모두 공격받고, 3×3은 가운데 칸이 나머지 여덟 칸을 모두 공격해 쓸 수 없는 데다 한 줄에 하나씩 놓는 여섯 가지를 전부 따져도 대각선이 겹칩니다. N = 1과 N ≥ 4는 언제나 배치가 있습니다.

N이 하나 늘 때마다 대략 다섯 배가 됩니다. N = 10이 724가지, N = 12가 14,200가지, N = 14가 365,596가지입니다. 마지막으로 세어진 값은 N = 27이고(2016년, 여러 대를 나눠 쓴 계산), 그보다 큰 N을 빠르게 세는 방법은 알려져 있지 않습니다.

한 줄에 하나씩 놓는다고 두면 남는 제약이 열과 두 대각선뿐이라, 그 셋을 비트로 들고 다니면 됩니다. 한 줄 내려갈 때마다 대각선 마스크가 좌우로 한 칸씩 밀리므로 시프트 한 번으로 갱신되고, 놓을 수 있는 자리는 세 값을 OR한 것의 여집합입니다. 대각선을 매번 훑지 않아도 되어 N = 14까지 즉시 나옵니다.

다릅니다. 배치 하나를 찾는 것은 아주 큰 N에서도 쉽고, N ≥ 4라면 공식으로 바로 적어 내는 방법까지 알려져 있습니다. 반면 전부 세는 것은 N이 늘 때마다 다섯 배씩 불어나 지금도 N = 27이 한계입니다.

판을 90도씩 네 번 돌린 것과 각각의 거울상, 모두 여덟 가지를 한 무리로 봅니다. 이 도구는 여덟 가지 가운데 사전순으로 가장 앞선 것을 대표로 삼아 세므로, 같은 무리에 속한 배치는 어느 것을 넣어도 같은 대표로 모입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.