数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究数字连接游戏？
数字连接是一种逻辑谜题，涉及在网格中找到连接数字的路径。
一个简单的数字连接谜题示例 数字连接谜题的解答
规则 − 玩家必须使用单一的连续线（或路径）将网格上所有匹配的数字配对。线条不能分叉或交叉，数字必须位于每条线的末端（即，不能位于中间）。只有当谜题有唯一的解且网格中的所有单元格都被填充时，才认为该谜题设计良好，尽管一些数字连接设计者没有规定这一点。
游戏 − 考虑一个 n × n 的方格阵列。一些方格是空的，一些是实心的，一些非实心的方格被标记为整数 1、2、3、… 每个整数在棋盘上占据两个不同的方格。玩家的任务是使用仅水平和垂直移动的简单路径连接棋盘上每个整数的两个出现位置。不允许两条不同的路径相互交叉。任何路径都不能包含任何实心方格（实心方格被禁止出现在任何路径上）。最后，所有非实心方格都必须被路径填充。
算法 − 要准备一个给定棋盘大小 n × n 的有效随机谜题，我们首先在棋盘上生成随机的简单且互不交叉的路径。如果一些孤立的方格位于所有生成的路径之外，则将这些孤立的方格标记为实心（禁止）。然后，我们提供路径的端点和实心方格的列表作为谜题。
因此，我们首先生成一个解，然后从解中推导出谜题。路径和实心方格对 n × n 棋盘进行分区。我们使用联合查找数据结构来生成此分区。该数据结构处理棋盘上 n^2 个方格集合的子集。
解释
在棋盘上随机定位方格 (i, j) 和 (k, l)，条件是：(a) (i, j) 和 (k, l) 彼此相邻，并且 (b) (i, j) 和 (k, l) 均不属于迄今为止生成的任何路径。如果在整个棋盘上找不到这样的方格对，则返回失败 /* 在这里，(i, j) 和 (k, l) 是要构造的新路径上的前两个方格。*
将包含 (i, j) 和 (k, l) 的两个联合查找树合并。
重复执行，只要当前路径可以扩展：将 (i, j) 重命名为 (k, l)。定位 (i, j) 的随机相邻方格 (k, l)，条件是：(a) (k, l) 不属于迄今为止生成的任何路径（包括当前路径）(b) (k, l) 在部分构造的当前路径上唯一的邻居是 (i, j)。
如果找不到这样的邻居 (k, l)，则路径无法进一步扩展，因此退出循环
否则，将 (i, j) 和 (k, l) 所属的两个联合查找树合并。
设置新路径开头和结尾处的两个方格的端点标志。
返回成功
输入
| || || || || || || 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
",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
",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
",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
",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
",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
",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
",stat);
if(stat) {
flag=1;
break;
}
}
}
ct++;
}
//printf("flag- %d
",flag);
if(flag==0)
return -1;
if(flag) {
//printf("value sent- %d
", 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
",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:
");
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("
");
}
printf("
The solution to the above table:
");
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("
");
}
}
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;
}
更新于： 2020年7月2日
572 次查看
广告