가지치기 탐색

체스의 퀸은 가로, 세로, 대각선으로 몇 칸이든 움직여 공격한다. 8 × 8 판에 퀸 8개를 서로 공격하지 않게 놓는 방법을 찾으려 한다. 행마다 퀸을 하나씩 놓는다고 해도, 행마다 8칸 가운데 하나를 고르면 \(8^8\), 곧 약 1677만 가지이다. 이것을 모두 놓아 보고 검사하는 것은 낭비처럼 보인다. 첫 두 행의 퀸이 이미 서로 공격한다면, 나머지 여섯 행을 어떻게 놓든 답이 될 수 없기 때문이다. 이런 경우를 어떻게 미리 알아보고 버릴 수 있을까?

판의 크기 n (n × n, 퀸 n개)

3.2.1백트래킹

백트래킹은 상태 공간 트리를 깊이 우선으로 훑되, 지금까지의 결정만으로 이미 조건을 어긴 상태에 이르면 그 아래 가지를 더 살피지 않고 바로 되돌아오는 탐색이다. N-퀸 문제에서는 위의 행부터 퀸을 하나씩 놓으며, 새 퀸이 앞의 퀸들과 같은 열이나 같은 대각선에 있으면 그 칸을 버린다. 그 행의 어느 칸에도 놓을 수 없으면 한 행 위로 되돌아가 그 퀸을 다음 칸으로 옮긴다. 이렇게 실패가 확실한 가지를 일찍 잘라 내는 것을 가지치기라 한다.

그림 1에서 판의 크기를 바꾸어 보자. 8 × 8에서 완전 탐색은 약 1677만 가지이지만, 백트래킹은 2천 개 남짓의 상태만 방문하고 92개의 해를 모두 찾는다. 8천 배 넘게 일이 준다. 퀸 하나를 놓을 때마다 그 열과 두 대각선이 막혀, 다음 행에서 놓을 수 있는 칸이 빠르게 줄기 때문이다. 판이 커질수록 그 차이는 더 크게 벌어진다.¹

3.2.2더 좋은 답이 나올 수 없는 가지

가방 문제처럼 가장 좋은 답을 찾는 문제에서는 조건을 어긴 가지뿐 아니라, 더 좋은 답이 나올 수 없는 가지도 버린다. 지금까지 찾은 가장 큰 가치가 90인데, 어떤 가지에서 남은 물건을 무게 제한 없이 모두 넣어도 가치가 80을 넘지 못한다면 그 가지는 볼 필요가 없다. 이때 '아무리 잘해도 얻을 수 있는 값'을 쉽게, 그러면서도 너무 낮지 않게 어림하는 것이 중요하다. 어림이 정확할수록 많은 가지를 자를 수 있지만, 어림이 틀려 실제보다 낮게 잡으면 답을 놓친다.

3.2.3예제 풀이

첫 행 1열에 놓으면 둘째 행의 1열(같은 열)과 2열(대각선)이 막혀 3열에 놓는다. 셋째 행은 1, 3열(열), 2, 4열(대각선)이 모두 막혀 되돌아간다. 둘째 행을 4열로 옮기면 셋째 행은 2열만 가능하고, 넷째 행은 모든 칸이 막힌다. 그래서 첫 행 1열에서는 해가 없다.

첫 행을 2열로 옮기면 둘째 행은 4열, 셋째 행은 1열, 넷째 행은 3열에 놓을 수 있어 해 (2, 4, 1, 3)을 찾는다. 완전 탐색이라면 \(4^4 = 256\)가지를 모두 검사해야 했지만, 백트래킹은 막힌 칸에서 곧바로 돌아와 수십 개의 상태만 보았다. 즉 가지치기는 같은 답을 훨씬 적은 일로 찾게 해 준다. 그래서 스도쿠 풀이, 시간표 짜기, 퍼즐 같은 문제는 백트래킹으로 푼다.

아래 탐구 카드에서 N-퀸과 가방 문제를 백트래킹으로 풀고, 가지치기가 줄이는 일의 양을 재어 보자.

1. 8-퀸 문제는 1848년 체스 문제 작가 베첼이 처음 냈고, 수학자 가우스도 관심을 가졌다. 해는 92개이며, 판을 돌리거나 뒤집어 같아지는 것을 하나로 치면 12개이다.