여덟 여왕
여왕 여덟이 서로 노려봅니다
가로세로 8칸인 체스판에 여왕 말 8개를 놓아 보세요. 여왕은 가로, 세로, 대각선 어디로든 끝까지 움직여 상대를 잡을 수 있습니다.
여덟 여왕이 서로를 단 한 번도 공격할 수 없게 판 위에 모두 배치할 수 있을까요? 아무 생각 없이 놓다 보면 서너 개째에서 반드시 길이 막힙니다. 어떻게 길을 찾아야 할까요?
이야기
1848년 독일의 체스 잡지에 막스 베첼이 이 문제를 냅니다. 곧 가우스도 여기에 손을 댔습니다.
그런데 그 가우스가 개수를 틀렸습니다. 처음에 그는 답이 일흔여섯 가지라고 적었습니다. 나중에야 92가지로 고쳤습니다. 수학사에서 가장 셈을 잘하던 사람도 이런 종류의 문제 앞에서는 하나씩 세다가 빠뜨린 것입니다.
까닭은 이 문제에 공식이 없기 때문입니다. 줄마다 하나씩, 세로줄에도 하나씩이라는 것까지는 금방 압니다. 그러나 대각선은 규칙으로 정리되지 않아 결국 다 놓아 보는 수밖에 없습니다.
그래서 오늘도 판이 커지면 컴퓨터로 세는 것 말고는 길이 없습니다. 27×27 판의 답이 몇 가지인지 알아낸 것은 2016년이었고, 그 뒤로는 아직 아무도 못 셌습니다.
손으로 찾을 때 쓰는 방법에도 이름이 있습니다. 놓다가 막히면 되돌아가 다른 자리를 시도하는 것 — 백트래킹입니다. 컴퓨터가 미로를 풀 때, 스도쿠를 풀 때 쓰는 바로 그 방법입니다.
서로 부딪히지 않게 배치하는 문제의 표본입니다.
공장의 작업 일정 짜기, 항공기 이착륙 시간 배정, 시험 시간표 만들기가 모두 이 꼴이고, 컴퓨터는 되짚어 가기(백트래킹)로 풉니다.
계단 넷 — 같은 사실을 네 깊이로
작은 판에서 놓아 본다
먼저 작은 4×4 바둑판 모양을 그려 놓고 바둑돌 4개로 해 봅니다. 첫 번째 줄 아무 칸에 돌을 하나 놓으면, 그 돌의 가로·세로·대각선 길목에는 다른 돌을 놓을 수 없습니다.
돌을 하나 놓을 때마다 공격받지 않는 안전한 칸을 찾아 다음 줄에 놓아 봅니다. 4×4 판에서는 딱 2가지 배치만 가능함을 직접 손으로 찾아내며 빈칸이 줄어드는 규칙을 관찰해 보세요.
여왕을 놓아 보세요
2×2 와 3×3 은 아예 불가능합니다 — 자리가 너무 좁습니다.
경우를 빠짐없이 세기
8×8 판에서 각 행마다 여왕이 정확히 하나씩 들어가야 하므로 전체 경우의 수는 가지나 됩니다. 같은 열에 둘 수 없다는 조건만 써도 가지입니다.
사람이 이 많은 수를 다 놓아볼 수는 없습니다. 하지만 한 줄씩 여왕을 놓아가다가 대각선 충돌이 일어나는 순간 그 뒤를 더 보지 않고 바로 직전 단계로 되돌아가는 가지치기를 하면 따져볼 경우가 수백 번 안쪽으로 확 줄어듭니다.
아무렇게나 놓으면 얼마나 많나
4 천 8 백만 분의 1 — 조건이 얼마나 강한지 보입니다.
가지치기
이 탐색 전략을 백트래킹(Backtracking, 되추적 알고리즘)이라 부릅니다. 깊이 우선 탐색(DFS)을 진행하면서 해가 될 가능성이 없는 가지를 조기에 잘라내는(pruning) 기법입니다.
여왕의 위치를 순열 으로 둘 때, 대각선 충돌 조건은 입니다. 이 조건을 검사하는 효율적인 배열 구조를 설계하면 -여왕 문제의 전체 해(8×8의 경우 회전과 대칭을 고려한 기본해 12개, 전체 해 92개)를 체계적으로 모두 구할 수 있습니다.
서로 다른 답만 세면
나머지는 돌리거나 뒤집은 것입니다.
백트래킹
여덟 여왕 문제는 컴퓨터 과학에서 제약 만족 문제(CSP, Constraint Satisfaction Problem)의 대표적 본보기입니다. 복잡한 제약 조건 아래에서 가능한 상태 공간을 효율적으로 탐색하는 척도가 됩니다.
도널드 커누스의 댄싱 링크(Dancing Links, DLX) 알고리즘이나 SAT 솔버의 발전으로 수백만 크기의 -여왕 문제도 순식간에 해결할 수 있게 되었습니다. 반도체 회로 배치, 일정표 작성, 자원 배분 최적화의 밑바탕에 이 알고리즘이 있습니다.
얼마나 오래 걸리나
되돌아가기(backtracking) 로 가지를 쳐야 풀립니다.
풀어 보기
작은 체스판과 여왕. 크기가 4×4인 체스판의 각 행에 여왕을 하나씩 놓아 서로 공격하지 못하게 하려 한다.
(1) 크기가 2×2, 3×3인 체스판에서 각각 여왕 2개, 3개를 서로 공격하지 않게 놓을 수 있는지 판정하시오.
(2) 4×4 체스판에서 첫 번째 행 2번째 열(1, 2)에 첫 여왕을 놓았을 때, 나머지 세 행의 여왕 위치를 차례대로 구하시오.
(3) 4×4 체스판에서 서로 공격하지 않는 4-여왕의 서로 다른 배치 방법은 모두 몇 가지인지 구하시오.
(2) 1행 2열에 놓으면 2행은 4열, 3행은 1열, 4행은 3열에 놓을 때 충돌 없이 유일하게 완성됩니다.
답과 풀이 보기
(1) 둘 다 불가능합니다.
는 어느 두 칸을 골라도 같은 줄이거나 대각선입니다.
은 세 행에 하나씩 놓아 보면 반드시 대각선이 겹칩니다. (모든 배치를 따져 보면 0 가지입니다.)
(2) 1 행 2 열에서 시작하면 2 행 4 열 → 3 행 1 열 → 4 행 3 열 — 이 길 하나뿐입니다.
2 행에 3 열은 대각선이 겹치고, 1 열은 3 행·4 행이 막혀 끝까지 못 갑니다.
(3) 2 가지입니다 — 과 (열 번호를 행 순서대로 적은 것). 둘은 서로 좌우를 뒤집은 것입니다.
판이 커지면 8×8 은 92 가지가 됩니다. 그런데 4×4 는 겨우 둘, 2×2·3×3 은 아예 없습니다 — 작을수록 어렵습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
되짚기는 컴퓨터가 매일 하는 일입니다.
- 스도쿠 풀이 — 넣어 보고 막히면 되돌아옵니다
- 시간표·좌석 배치 — 조건을 만족하는 배치를 찾는 문제입니다
- 작은 판부터 — 4×4에 여왕 넷을 놓아 보세요. 두 가지뿐입니다
이어지는 장
체스판 위에서 서로 공격하지 못하도록 여덟 여왕을 배치하는 조합론적 문제는 체스판의 모든 칸을 한 번씩만 밟고 도는 제81장 과 함께 판 위의 말들이 엮어내는 깊은 수학적 아름다움을 보여 줍니다.
영감을 받은 곳
체스 작가 막스 베첼(Max Bezzel)이 1848년 『베를린 체스 신문』(Berliner Schachzeitung)에 처음 제안하고, 1850년 프란츠 나우크(Franz Nauck)가 92개의 모든 해를 찾아냈으며 카를 프리드리히 가우스가 깊이 연구한 고전 문제입니다.