数字连接是一种逻辑谜题，涉及在网格中找到连接数字的路径。
Numberlink谜题的一个简单例子 Numberlink谜题的解答
规则 – 玩家必须用单一连续线（或路径）将网格上的所有匹配数字配对。线条不能分叉或交叉，并且数字必须位于每条线的末端（即不在中间）。只有当问题具有唯一解并且网格中的所有单元格都填充时，才认为问题设计良好，尽管一些Numberlink设计师不规定这一点。
游戏 – 考虑一个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）部分构建的当前路径上（i, j）的唯一邻居是（k, l）。
如果找不到这样的邻居方块（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#include#include
Input:a nodeOutput: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 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 && j2path_number==0) { flag=1; break; } } cc++; case 1: i2= i1-0; j2= j1-1; if(j2>=0 && i2<n && j2path_number==0) { flag=1; break; } } cc++; case 2: i2= i1+1; j2= j1-0; if(i2<n && j2path_number==0) { flag=1; break; } } cc++; case 3: i2= i1-0; j2= j1+1; if(i2<n && j2path_number==0) { flag=1; break; } } cc++; case 4: if(cc==4) break; i2= i1-1; j2= j1-0; if(i2>=0 && i2<n && j2path_number==0) { flag=1; break; } } cc++; case 5: if(cc==4) break; i2= i1-0; j2= j1-1; if(j2>=0 && i2<n && j2path_number==0) { flag=1; break; } } cc++; case 6: if(cc==4) break; i2= i1+1; j2= j1-0; if(i2<n && j2path_number==0) { flag=1; break; } } cc++; case 7: if(cc==4) break; i2= i1-0; j2= j1+1; if(i2<n && j2path_number==0) { flag=1; break; } } cc++; } } if(flag==1) break; ct++; k++; } if(ct0 && findset(arr[i-1][j])==findset(arr[ii][jj])) ct++; if(i0 && findset(arr[i][j-1])==findset(arr[ii][jj])) ct++; if(j1) 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 && j2path_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 && j2path_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 && j2path_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 && j2path_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 && j2path_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 && j2path_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 && j2path_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 && j2path_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;jendpoint ==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;jpath_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;}
以上就是一个数字连线游戏？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445287.html
微信扫一扫 
支付宝扫一扫 
