넘버링크(Numberlink)는 격자 안에서 같은 숫자끼리 경로를 찾아 연결하는 논리 퍼즐입니다. 흔히 스마트폰 퍼즐 게임 '플로우(Flow Free)'의 원형으로도 알려져 있으며, 간단한 규칙 속에 깊은 사고력을 요구하는 것이 특징입니다.
넘버링크 퍼즐이란?
아래는 넘버링크 퍼즐의 간단한 예시와 그 해답입니다.
왼쪽이 퍼즐 문제, 오른쪽이 그 정답입니다. 같은 숫자가 하나의 연속된 선으로 연결되어 있는 것을 확인할 수 있습니다.
기본 규칙
플레이어는 격자 위에 있는 같은 숫자끼리 하나의 연속된 선(경로)으로 모두 짝지어 연결해야 합니다. 이때 지켜야 할 규칙은 다음과 같습니다.
- 선은 분기하거나 서로 교차할 수 없습니다.
- 각 숫자는 반드시 선의 끝점에 위치해야 하며, 선 중간에 놓일 수 없습니다.
- 일반적으로 잘 설계된 문제라면 해답이 유일하고, 격자의 모든 칸이 채워져야 합니다. 다만 일부 제작자는 이 조건을 강제하지 않기도 합니다.
게임의 형식적 정의
n × n 크기의 격자를 생각해 봅시다. 격자의 칸 중 일부는 비어 있고, 일부는 막혀 있는(솔리드) 칸이며, 막히지 않은 칸 중 일부에는 1, 2, 3,… 과 같은 정수가 표시되어 있습니다. 각 정수는 보드 위의 정확히 두 개의 서로 다른 칸을 차지합니다.
플레이어의 과제는 다음과 같습니다.
- 각 정수가 놓인 두 칸을 수평·수직 이동만으로 구성된 단순 경로(simple path)로 연결합니다.
- 서로 다른 두 경로는 절대 교차할 수 없습니다.
- 경로에는 막힌 칸(솔리드 칸)이 포함될 수 없습니다.
- 모든 막히지 않은 칸은 반드시 경로로 채워져야 합니다.
퍼즐 생성 알고리즘
주어진 크기 n × n의 유효한 랜덤 퍼즐을 만들기 위해, 먼저 보드 위에 서로 교차하지 않는 랜덤한 단순 경로들을 생성합니다. 생성된 경로들 바깥에 고립된 칸이 남아 있다면, 그 칸들을 막힌 칸(금지 칸)으로 표시합니다. 그런 다음 경로들의 양 끝점과 막힌 칸 목록을 퍼즐로 제공합니다.
즉, 먼저 해답을 만들고, 그 해답으로부터 퍼즐을 역산하는 방식입니다. 경로와 막힌 칸들은 n × n 보드 전체를 분할(partition)하게 되는데, 이 분할을 생성하기 위해 유니온-파인드(Union-Find) 자료구조를 사용합니다. 이 자료구조는 보드 위 n²개 칸 집합의 부분집합들을 관리합니다.
알고리즘 단계별 설명
- 보드 위에 (i, j)와 (k, l) 두 칸을 무작위로 선택합니다. 조건은 다음과 같습니다. (a) 두 칸이 서로 이웃해야 하고, (b) 어느 쪽도 지금까지 생성된 어떤 경로에도 속하지 않아야 합니다. 보드 전체에서 그러한 칸 쌍을 찾지 못하면 FAILURE를 반환합니다. /* 여기서 (i, j)와 (k, l)은 새로 만들 경로의 처음 두 칸입니다. */
- (i, j)와 (k, l)이 속한 두 유니온-파인드 트리를 합칩니다(union).
- 현재 경로를 더 확장할 수 있는 동안 반복합니다: (i, j) = (k, l)로 이름을 바꾸고, (i, j)의 무작위 이웃 칸 (k, l)을 찾습니다. 조건은 (a) (k, l)이 지금까지 생성된 어떤 경로에도(현재 경로 포함) 속하지 않을 것, (b) 부분적으로 구성된 현재 경로에서 (k, l)이 가진 유일한 이웃이 (i, j)일 것입니다.
- 그런 이웃 (k, l)을 찾을 수 없으면 더 이상 경로를 확장할 수 없으므로 반복문을 종료합니다.
- 찾았다면 (i, j)와 (k, l)이 속한 두 유니온-파인드 트리를 합칩니다.
- 새 경로의 시작 칸과 끝 칸에 끝점(endpoint) 플래그를 설정합니다.
- SUCCESS를 반환합니다.
입력 예시
| || || || || || || 4 | | || || || || || 3 || | | || || 2 || 2 || || || 3 | | || || || || X || || 1 | | || || 6 || || || 7 || 7 | | 5 || 4 || || X || || X || 1 | | || 5 || || 6 || || || |
출력 결과 (정답)
| 4 || 4 || 4 || 4 || 4 || 4 || 4 | | 4 || 1 || 1 || 1 || 1 || 3 || 3 | | 4 || 1 || 2 || 2 || 1 || 1 || 3 | | 4 || 1 || 1 || 1 || X || 1 || 1 | | 4 || 4 || 6 || 1 || 1 || 7 || 7 | | 5 || 4 || 6 || X || 1 || X || 1 | | 5 || 5 || 6 || 6 || 1 || 1 || 1 |
C 언어 구현 예제
다음은 위 알고리즘을 C 언어로 구현한 전체 코드입니다. 유니온-파인드 기반으로 랜덤 넘버링크 퍼즐과 그 해답을 함께 출력합니다.
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct _node {
struct _node *parent;
int rank;
int path_number;
int endpoint;
};
typedef struct _node node;
/* Name: initboard()
Input: 2D-array of pointers, size of array row/column
Output: --void--
Description: Takes a table of pointers and initializes it. */
void initboard(node ***arr, int n) {
int i, j;
for (i=0;i<n;i++){
for (j=0;j<n;j++){
node *np;
np = (node *)malloc(sizeof(node));
np->rank = 0;
np->parent = NULL;
np->path_number = 0;
np->endpoint = 0;
arr[i][j] = np;
}
}
}Input:a node Output:the set pointer of the set the node belongs to
Description − 노드를 입력받아 해당 노드가 속한 집합의 포인터를 반환합니다. */
node *findset(node *n) {
if (n->parent != NULL)
n = n->parent;
return n;
}
void setunion(node *x, node *y) {
x = findset(x);
y = findset(y);
if (x->rank > y->rank)
y->parent = x;
else {
x->parent = y;
if(x->rank == y->rank)
y->rank++;
}
}
int neighbour(int n, node ***arr) {
int i1, i2, j1, j2, ct = 0, flag = 0, a, b,k2;
int k = rand()%(n*n);
while (ct < (n*n)) {
k %= (n*n);
i1 = k/n;
j1 = k%n;
if (arr[i1][j1]->path_number==0) {
int kk = rand()%4;
int cc = 0;
switch (kk) {
case 0: i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 1: i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 2: i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 3: i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 4: if(cc==4)
break;
i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 5: if(cc==4)
break;
i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 6: if(cc==4)
break;
i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
case 7: if(cc==4)
break;
i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
flag=1;
break;
}
}
cc++;
}
}
if(flag==1)
break;
ct++;
k++;
}
if(ct<n*n) {
k2= (i2*n)+j2;
return k*(n*n)+k2;
} else {
return -1;
}
}int checkneigh(int k1, int k2, int n, node ***arr) {
int i= k2/n;
int j= k2%n;
int ii= k1/n;
int jj= k1%n;
int ct=0;
if(i>0 && findset(arr[i-1][j])==findset(arr[ii][jj]))
ct++;
if(i<n-1 && findset(arr[i+1][j])==findset(arr[ii][jj]))
ct++;
if(j>0 && findset(arr[i][j-1])==findset(arr[ii][jj]))
ct++;
if(j<n-1 && findset(arr[i][j+1])==findset(arr[ii][jj]))
ct++;
if(ct>1)
return 0;
else
return 1;
}
int valid_next(int k, int n, node ***arr) {
int i1, i2, j1, j2, a, b, kk, stat,ct=0;
int flag=0;
i1= k/n;
j1= k%n;
kk= rand()%4;
switch(kk) {
case 0: i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 1: i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 2: i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 3: i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 4: if(ct==4)
break;
i2= i1-1;
j2= j1-0;
if(i2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 5: if(ct==4)
break;
i2= i1-0;
j2= j1-1;
if(j2>=0 && i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 6: if(ct==4)
break;
i2= i1+1;
j2= j1-0;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
case 7: if(ct==4)
break;
i2= i1-0;
j2= j1+1;
if(i2<n && j2<n) {
if(arr[i2][j2]->path_number==0) {
stat= checkneigh(k, (n*i2 + j2),n,arr);
//printf("%d\n",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
}
//printf("flag- %d\n",flag);
if(flag==0)
return -1;
if(flag) {
//printf("value sent- %d\n", i2*n + j2);
return (i2*n)+j2;
}
}int addpath(node ***arr, int n, int ptno) {
int a,b,k1,k2;
int i1,j1,i2,j2;
k2= neighbour( n, arr);
if(k2==-1) //no valid pair found to start with
return 0;
k1= k2/(n*n);
k2= k2%(n*n);
//printf("%d %d\n",k1,k2);
i1= k1/n;
j1= k1%n;
i2= k2/n;
j2= k2%n;
arr[i1][j1]->endpoint= 1;
arr[i2][j2]->path_number= ptno;
arr[i1][j1]->path_number= ptno;
node *n1, *n2;
n1= arr[i1][j1];
n2= arr[i2][j2];
n1= findset(n1);
n2= findset(n2);
setunion(n1, n2);
while(1) {
i1= i2;
j1= j2;
k1= (i1*n)+j1;
k2= valid_next(k1,n,arr);
if(k2==-1) {
arr[i1][j1]->endpoint= 1;
break;
}
i2=k2/n;
j2=k2%n;
arr[i2][j2]->path_number= ptno;
node *n1, *n2;
n1= arr[i1][j1];
n2= arr[i2][j2];
n1= findset(n1);
n2= findset(n2);
setunion(n1,n2);
}
return 1;
}
void printtable(node ***arr, int n) {
int i,j;
printf("Table to be solved:\n");
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(arr[i][j]->endpoint ==1){
if(arr[i][j]->path_number/10==0)
printf("| %d |",arr[i][j]->path_number);
else
printf("| %d|",arr[i][j]->path_number);
} else if(arr[i][j]->path_number==0)
printf("| X |");
else
printf("| |");
}
printf("\n");
}
printf("\n\nThe solution to the above table:\n");
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(arr[i][j]->path_number != 0){
if(arr[i][j]->path_number/10==0)
printf("| %d |",arr[i][j]->path_number);
else
printf("| %d|",arr[i][j]->path_number);
} else
printf("| X |");
}
printf("\n");
}
}
int main(void) {
srand((unsigned int) time (NULL));
int i, j;
int ct = 1;
int n = 7;
node*** pointers= (node ***)malloc(n*sizeof(node **));
for (i=0; i<n; i++)
pointers[i] = (node **)malloc(n*sizeof(node *));
initboard(pointers, n);
while(1) {
i = addpath(pointers, n, ct);
if (i==0) {
break;
} else {
ct++;
}
}
printtable(pointers,n);
return 0;
}이 코드는 7×7 크기의 보드에서 시작하여, 더 이상 새 경로를 추가할 수 없을 때까지 addpath() 함수를 반복 호출합니다. 실행이 끝나면 풀어야 할 퍼즐(끝점 숫자와 금지 칸만 표시)과 그 정답(전체 경로)이 차례로 출력됩니다.
마무리
넘버링크는 규칙은 단순하지만, 유일해를 보장하면서 모든 칸을 채우는 퍼즐을 설계하는 것은 생각보다 까다로운 작업입니다. 본문에서 소개한 것처럼 '정답을 먼저 생성하고 문제를 역산하는' 방식은 그 대표적인 해법이며, 유니온-파인드 자료구조를 활용하면 경로들이 서로 충돌하지 않도록 효율적으로 관리할 수 있습니다. 직접 코드를 실행해 보며 다양한 크기의 퍼즐을 생성해 보는 것도 좋은 학습 경험이 될 것입니다.