一个数字连线游戏？

数字连接是一种逻辑谜题，涉及在网格中找到连接数字的路径。

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），则路径无法进一步延伸，因此跳出循环

  

  Ztoy网络商铺多用户版

  在原版的基础上做了一下修正：增加1st在线支付功能与论坛用户数据结合，vip也可与论坛相关，增加互动性vip会员的全面修正评论没有提交正文的问题特价商品的调用连接问题删掉了2个木马文件去掉了一个后门补了SQL注入补了一个过滤漏洞浮动价不能删除的问题不能够搜索问题收藏时放入购物车时出错点放入购物车弹出2个窗口修正定单不能删除问题VIP出错问题主题添加问题商家注册页导航连接问题添加了导航FLASH源文

  下载

• 否则，将包含（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
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;irank = 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 && i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 1: i2= i1-0;
               j2= j1-1;
            if(j2>=0 && i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 2: i2= i1+1;
            j2= j1-0;
            if(i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 3: i2= i1-0;
            j2= j1+1;
            if(i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 4: if(cc==4)
               break;
            i2= i1-1;
            j2= j1-0;
            if(i2>=0 && i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 5: if(cc==4)
               break;
            i2= i1-0;
            j2= j1-1;
            if(j2>=0 && i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 6: if(cc==4)
               break;
            i2= i1+1;
            j2= j1-0;
            if(i2path_number==0) {
                  flag=1;
                  break;
               }
            }
            cc++;
            case 7: if(cc==4)
               break;
            i2= i1-0;
            j2= j1+1;
            if(i2path_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 && i2path_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 && i2path_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(i2path_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(i2path_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 && i2path_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 && i2path_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(i2path_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(i2path_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;iendpoint ==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;ipath_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