문제 이해
주어진 그림의 여덟 개 빈 칸에 숫자 1, 2, 3, 4, 5, 6, 7, 8을 하나씩 배치하려고 합니다. 단, 수열에서 서로 이웃한 숫자(1과 2, 2와 3 등)가 그리드에서 인접한 칸에 놓여서는 안 됩니다. 인접 판단에는 상하좌우뿐 아니라 대각선 방향도 포함됩니다.
예를 들어 입력이 다음과 같은 3×4 그리드라면, 값 0은 사용하지 않는 칸, -1(NOTCONSIDERED)은 아직 숫자가 채워지지 않은 칸을 의미합니다.
| 0 | - 1 | - 1 | 0 |
| - 1 | - 1 | - 1 | - 1 |
| 0 | - 1 | - 1 | 0 |
이때 출력 결과는 다음과 같습니다.
해결 접근 방법
이 문제는 전형적인 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 각 빈 칸에 숫자 1부터 8까지 차례로 넣어 보고, 조건을 위반하면 이전 단계로 되돌아가 다른 숫자를 시도하는 방식입니다. 전체 탐색 공간은 최대 8! = 40,320가지 순열이므로 충분히 빠르게 해를 찾을 수 있습니다.
알고리즘의 핵심 구성 요소는 다음과 같습니다.
- N = 3, M = 4: 그리드의 행과 열 크기를 정의합니다.
- NOTCONSIDERED = -1: 아직 숫자가 채워지지 않은 칸을 표시하는 값입니다.
- present_in_grid(): 특정 숫자가 이미 그리드에 존재하는지 확인하는 함수입니다. 같은 숫자가 중복 배치되는 것을 방지합니다.
- isSafe(): 현재 위치(row, col)에 숫자 num을 놓을 수 있는지 검사합니다. 여덟 개의 유효한 위치인 (0,1), (0,2), (1,0), (1,3), (2,1), (2,2), (1,1), (1,2)는 각각 인접한 칸의 집합이 다르므로, 위치별로 인접 칸을 개별적으로 처리합니다. 인접 칸의 숫자와의 절댓값 차이가 1 이하이거나, num이 이미 그리드에 존재한다면 false를 반환합니다.
- search_free_location(): 그리드를 왼쪽에서 오른쪽, 위에서 아래로 스캔하여 아직 채워지지 않은(NOTCONSIDERED) 첫 번째 칸의 좌표를 참조로 반환합니다. 더 이상 빈 칸이 없으면 false를 반환합니다.
- Solve(): 백트래킹을 수행하는 핵심 재귀 함수입니다. 빈 칸이 더 없으면 true를 반환해 성공을 알리고, 그렇지 않으면 1부터 8까지의 숫자에 대해 isSafe() 검사를 통과하면 배치한 뒤 자기 자신을 재귀 호출합니다. 이후 단계가 실패하면 해당 칸을 NOTCONSIDERED로 되돌리고 다음 숫자를 시도합니다.
예시 구현
더 나은 이해를 돕기 위해 다음 C++ 구현을 살펴보겠습니다.
#include <cmath>
#include <iostream>
#define N 3
#define M 4
#define NOTCONSIDERED -1
using namespace std;
bool present_in_grid(int grid[N][M], int num) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
if (grid[i][j] == num)
return true;
}
return false;
}
bool isSafe(int grid[N][M], int row, int col, int num) {
if (row == 0 && col == 1) {
if (present_in_grid(grid, num) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1))
return false;
}
else if (row == 0 && col == 2) {
if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1))
return false;
}
else if (row == 1 && col == 0) {
if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1))
return false;
}
else if (row == 1 && col == 3) {
if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1))
return false;
}
else if (row == 2 && col == 1) {
if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1))
return false;
}
else if (row == 2 && col == 2) {
if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row - 1][col - 1]) <= 1))
return false;
}
else if (row == 1 && col == 1) {
if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1))
return false;
}
else if (row == 1 && col == 2) {
if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1))
return false;
}
return true;
}
bool search_free_location(int grid[N][M], int& row, int& col) {
for (row = 0; row < N; row++)
for (col = 0; col < M; col++) {
if (grid[row][col] == NOTCONSIDERED)
return true;
}
return false;
}
void show_res(int grid[N][M]) {
for (int i = 0; i < N; i++) {
if (i == 0 || i == N - 1)
cout << " ";
for (int j = 0; j < M; j++) {
if (grid[i][j] == 0)
cout << " ";
else
cout << grid[i][j] << " ";
}
cout << endl;
}
}
bool Solve(int grid[N][M]) {
int row, col;
if (!search_free_location(grid, row, col))
return true;
for (int num = 1; num <= 8; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (Solve(grid))
return true;
grid[row][col] = NOTCONSIDERED;
}
}
return false;
}
int main(){
int grid[N][M] = { { 0, -1, -1, 0 },
{ -1, -1, -1, -1 },
{ 0, -1, -1, 0 } };
if (Solve(grid))
show_res(grid);
else
cout << "Not possible";
}입력
{ { 0, -1, -1, 0 },
{ -1, -1, -1, -1},
{ 0, -1, -1, 0 }}출력
3 5 7 1 8 2 4 6
출력 결과 분석
첫째 줄과 셋째 줄 맨 앞의 공백은 사용하지 않는 모서리 칸(값 0)을 나타냅니다. 실제 배치 결과를 그리드 좌표로 옮기면 다음과 같습니다.
[0, 3, 5, 0] [7, 1, 8, 2] [0, 4, 6, 0]
모든 인접 칸(대각선 포함)의 숫자 차이가 2 이상임을 확인할 수 있습니다. 예를 들어 3의 이웃은 5, 7, 1, 8이며, 연속 수인 2와 4는 어디에도 붙어 있지 않습니다. 만약 조건을 만족하는 배치가 존재하지 않는다면 Solve() 함수는 false를 반환하고 프로그램은 "Not possible"을 출력합니다.