8퀸 문제 소개 | 백트래킹과 n퀸 문제

1848년의 체스 퍼즐

독일의 체스 문제 작가 막스 베첼은 1848년 베를린의 한 체스 잡지에 이 퍼즐을 냈습니다. 프란츠 나우크는 1850년에 92가지 풀이를 모두 발표하고, 더 큰 판에 대해서도 같은 질문을 던졌습니다. 카를 프리드리히 가우스는 이 퍼즐을 관심 있게 지켜보았고 편지에서 이에 대해 논했습니다.

가로줄과 세로줄마다 퀸 하나

서로 공격하지 않는 퀸 8개는 서로 다른 가로줄 8개와 서로 다른 세로줄 8개에 있어야 합니다. 그래서 풀이는 1부터 8까지의 수를 섞어 놓은 것, 곧 순열에 규칙 하나를 더한 것입니다. 어느 두 퀸도 같은 대각선에 있으면 안 된다는 규칙입니다. 40,320개의 순열 가운데 이 규칙을 통과하는 것은 92개뿐입니다.

백트래킹

백트래킹은 풀이를 한 조각씩 쌓아 가다가 막다른 길에 부딪히는 순간 뒤로 물러납니다. 퀸의 경우에는 이렇습니다. 다음 줄의 첫 번째 안전한 칸에 퀸을 놓고, 어떤 줄에 안전한 칸이 없으면 윗줄로 돌아가 그 퀸을 앞으로 옮깁니다. 1972년 에츠허르 다익스트라는 바로 이 탐색으로 이 퍼즐을 이용해 구조적 프로그래밍을 설명했습니다.

대칭

판을 4분의 1바퀴 돌리거나 뒤집어도 풀이는 여전히 풀이입니다. 그래서 풀이마다 최대 8가지 모습이 생깁니다. 92가지 풀이는 이런 그룹 12개로 나뉩니다. 11개는 풀이가 8개씩이고, 하나는 4개뿐인데, 그 풀이는 반 바퀴 돌려도 똑같아 보이기 때문입니다.

n퀸 문제

n×n 판에서는 퀸 n개로 같은 질문을 합니다. 4 이상의 모든 n에 풀이가 있고, 그 수는 빠르게 늘어납니다. 4×4는 2가지, 8×8은 92가지, 12×12는 14,200가지입니다. 그 수를 구하는 공식은 알려져 있지 않으며, 기록 값은 대규모 컴퓨터 탐색으로 얻은 것입니다.

PictorX에서 해 보기

8퀸을 열고 칸을 클릭해 퀸을 놓으세요. 다시 클릭하면 치워집니다. ‘공격 범위 표시’는 내 퀸이 공격하는 칸에 점을 찍고, 빨간 퀸은 서로 공격하고 있습니다. ‘풀기’는 백트래킹 탐색을 한 단계씩 실행하며, 직접 놓은 퀸은 그대로 둡니다. ‘다음 풀이’는 모든 풀이를 차례로 보여 주고, ‘크기’는 판을 4×4부터 12×12까지 바꿉니다.

자주 묻는 질문

8퀸 문제는 누가 만들었나요?

독일의 체스 문제 작가 막스 베첼이 1848년에 만들었습니다. 프란츠 나우크가 1850년에 처음으로 전체 풀이를 발표했습니다.

풀이는 몇 가지인가요?

표준 판에서는 92가지입니다. 회전과 대칭을 하나로 치면 12가지입니다.

6×6 판은 왜 풀이가 이렇게 적나요?

풀이가 4가지뿐이며, 모두 한 그룹에 속합니다. 더 작은 5×5 판은 10가지입니다. 판이 클수록 풀이가 점점 많아져서 7×7은 40가지, 8×8은 92가지입니다.

PictorX가 무언가 업로드하나요?

아니요. 판은 브라우저의 캔버스에 그려집니다. ‘저장’은 PNG를 받고, ‘편집’은 그 이미지를 PictorX 편집기에서 엽니다.

관련 도구

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

8퀸 해 보기