초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
스도쿠처럼 정해진 풀이 없이 채운 판이 답인지 확인만 할 수 있는 문제가 많습니다. 그럴 때는 경우의 수 글의 완전 탐색처럼 경우를 하나씩 만들어 봐야 하는데, 경우는 금방 감당할 수 없이 많아집니다. 빠짐없이, 그러면서도 덜 헤매며 만들 수는 없을까요?
체스의 퀸은 가로, 세로, 대각선으로 몇 칸이든 가서 그 줄의 말을 잡습니다. n×n 판에 퀸 n개를 서로 잡을 수 없게 놓는 문제를 N-퀸 문제라 합니다.
퀸 4개를 놓아 봅시다.
칸을 누르면 퀸을 놓고, 퀸을 다시 누르면 뺍니다. 점은 놓인 퀸이 잡을 수 있는 칸이라 놓을 수 없습니다.
한 가로줄에 퀸이 둘이면 서로 잡으니, 줄마다 꼭 하나씩 놓입니다. 4×4면 줄마다 4칸 중 하나를 골라 곱의 법칙으로 4⁴ = 256가지, 8×8이면 1,600만 가지가 넘습니다.
줄마다 하나씩 고르는 일을 재귀로 적어 봅시다. place(row)는 row번 줄부터 끝
줄까지 퀸을 놓습니다. 줄은 0번부터 셉니다. safe는 위 줄의 퀸과 같은 세로줄이나
대각선에 있는지 봅니다. 두 칸의 가로 거리와 세로 거리가 같으면 같은
대각선입니다.
출력 없음row와 col이 어떻게 바뀌는지 따라가 봅시다.
safe는 끝 줄까지 다 놓은 뒤가 아니라 놓을 때마다 확인합니다. 둘째 줄에서
이미 잡히는 배치라면 아래 줄을 어떻게 채워도 답이 될 수 없으니, 더 들어가지 않고
다음 칸으로 넘어갑니다. 한 줄의 모든 칸이 막히면 함수가 끝나 윗줄로 돌아가고,
윗줄의 퀸이 옆 칸으로 옮겨 갑니다.
아직 아무 칸도 살펴보지 않았습니다.
X는 위 줄 퀸에게 잡혀 못 놓는 칸, 굵은 테두리는 그 칸을 잡는 퀸입니다.
이렇게 경우를 재귀로 만들어 가다 답이 될 수 없는 길을 알아채는 즉시 되돌아가는 방법을 백트래킹(backtracking)이라 합니다. 안 될 길을 잘라 내는 것은 가지치기(pruning)라 합니다.
답은 2개이고, 가지치기로 살펴보는 칸은 약 6분의 1입니다.
8×8에서 끝 줄까지 다 놓은 뒤 확인하면 칸을 1,900만 번 넘게 살펴보지만, 놓을 때마다 확인하면 15,720번이면 92가지 답을 모두 찾습니다. 가지치기를 해도 살펴보는 칸은 n이 하나 늘 때마다 몇 배씩 늘어납니다. 그래도 일찍 자를수록 크게 줄어듭니다.
글의 safe를 위 줄 퀸과 같은 세로줄인지만 보도록 바꾸고, 대각선은 printf 하기 직전에 한꺼번에 확인합니다. 이렇게 바꾼 프로그램으로 5×5 판에서 place(0)을 부르면 safe는 모두 몇 번 불릴까요? 숫자로 답하세요.