숫자 연결은 그리드에서 숫자를 연결하는 경로를 찾는 것과 관련된 논리 퍼즐 유형입니다.
Numberlink 퍼즐의 간단한 예 Numberlink 퍼즐에 대한 솔루션
규칙 − 플레이어는 그리드의 일치하는 모든 숫자를 단일 연속 라인(또는 경로)과 짝을 지어야 합니다. 선은 분기되거나 서로 교차할 수 없으며 숫자는 각 선의 끝에 있어야 합니다(즉, 중간이 아님). 일부 Numberlink 디자이너는 이를 규정하지 않지만 고유한 솔루션이 있고 그리드의 모든 셀이 채워져야 문제가 잘 설계된 것으로 간주됩니다.
게임 − n × n 정사각형 배열을 고려하십시오. 정사각형 중 일부는 비어 있고 일부는 실선이며 일부가 아닌 정사각형은 정수 1, 2, 3, …으로 표시됩니다. 각 정수는 보드에서 정확히 두 개의 다른 정사각형을 차지합니다. 플레이어의 임무는 수평 및 수직 이동만을 사용하여 간단한 경로로 보드에 있는 각 정수의 두 발생을 연결하는 것입니다. 두 개의 다른 경로가 서로 교차할 수 없습니다. 경로에는 솔리드 정사각형이 포함될 수 없습니다(단색 정사각형은 모든 경로에 표시되는 것이 금지됨). 마지막으로, 솔리드가 아닌 모든 사각형은 경로로 채워져야 합니다.
알고리즘 − 주어진 보드 크기 n × n으로 유효한 무작위 퍼즐을 준비하기 위해 먼저 보드에 서로 교차하지 않는 임의의 단순 경로를 생성합니다. 생성된 모든 경로 외부에 몇 개의 격리된 사각형이 남아 있는 경우 이러한 격리된 사각형을 솔리드(금지)로 표시합니다. 그런 다음 경로의 끝점과 실선 사각형 목록을 퍼즐로 제공합니다.
따라서 우리는 먼저 솔루션을 생성한 다음 솔루션에서 퍼즐을 해결합니다. 경로와 정사각형은 n × n 보드를 나눕니다. 우리는 이 파티션을 생성하기 위해 union-find 데이터 구조를 사용합니다. 데이터 구조는 보드에 있는 n^2 정사각형 세트의 부분집합을 다룹니다.
설명
-
(a) (i, j) 및 (k, l)이 서로 이웃이고 (b) 둘 다 (i, j)가 아닌 정사각형 (i, j) 및 (k, l)을 보드에서 무작위로 찾습니다. nor (k, l)은 지금까지 생성된 경로에 속하지 않습니다. 전체 보드에서 이러한 사각형 쌍이 발견되지 않으면 FAILURE를 반환합니다. /* 여기서 (i, j) 및 (k, l)은 구성할 새 경로의 처음 두 사각형입니다. *
-
(i, j) 및 (k, l)을 포함하는 두 개의 합집합 찾기 트리의 합집합을 만듭니다.
-
현재 경로가 확장될 수 있는 한 반복합니다. 이름 바꾸기 (i, j) =(k, l). (a) (k, l)이 지금까지 생성된 경로(현재 경로 포함)에 속하지 않도록 (i, j)의 임의의 이웃 정사각형(k, l)을 찾습니다. (b) 유일한 이웃(k , l) 부분적으로 구성된 현재 경로는 (i, j)입니다.
-
그러한 이웃(k, l)을 찾을 수 없으면 경로를 더 이상 확장할 수 없으므로 루프를 끊습니다.
-
그렇지 않으면 (i, j) 및 (k, l)이 속하는 두 개의 union-find 트리의 합집합을 만듭니다.
-
새 경로의 시작과 끝에 있는 두 사각형의 끝점 플래그를 설정합니다.
-
반환 성공
입력
| || || || || || || 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 |
예시
#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
설명 − 노드를 가져와서 설정된 포인터를 반환합니다. */
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;
}