A number-matching game?

Number Connect is a logic puzzle that involves finding paths connecting numbers in a grid.

A simple example of Numberlink puzzle Solution to Numberlink puzzle

Rules - Players must match all matching numbers on the grid with a single continuous line (or path). Lines cannot diverge or cross, and the numbers must be at the end of each line (i.e. not in the middle). A problem is considered well designed only if it has a unique solution and all cells in the grid are filled, although some Numberlink designers do not specify this.

Game - Consider an n×n array of blocks. Some of the squares are empty, some are solid, and some non-solid squares are marked by integers 1, 2, 3,... Each integer occupies two different squares on the board. The player's task is to connect the two occurrences of each integer on the board via a simple path using only horizontal and vertical movements. Two different paths are not allowed to intersect. No path can contain any solid blocks (no solid blocks are allowed on any path). Finally, all non-solid squares must be filled by paths.

Algorithm - To prepare an efficient random puzzle given a board size n×n, we first generate random simple disjoint paths on the board. If there are several isolated blocks that remain outside all generated paths, mark these isolated blocks as solid (forbidden). We then use the endpoints of the path and the list of solid squares as the puzzle.

So, we first generate a solution and then solve the puzzle from the solution. Paths and solid squares divide the n×n chessboard into parts. We use the union-lookup data structure to generate this split. The data structure handles a subset of n^2 squares on the chessboard.

Explanation

• Randomly find squares (i, j) and (k, l) on the chessboard such that: (a) (i, j) and (k , l) are neighbors of each other, and (b) neither (i, j) nor (k, l) belong to any path generated so far. If no such pair of squares is found on the entire board, a failure is returned /* Here, (i, j) and (k, l) are the first two squares of the new path to be constructed. *

• Merge two union-find trees containing (i, j) and (k, l).

• Repeat the following steps until the current path cannot be extended: Rename (i, j) to (k, l). Randomly find the neighbor squares (k, l) of (i, j) such that: (a) (k, l) does not belong to any path generated so far (including the current path) (b) On the current path constructed in part ( The only neighbor of i, j) is (k, l).

• If no such neighbor square (k, l) is found, the path cannot be extended further, so the loop is jumped out

• Otherwise, the Merge two union-find trees containing (i, j) and (k, l).

• Set the flags of the starting and ending blocks of the new path.

• Return successfully

Input

| || || || || || || 4 |
| || || || || || 3 || |
| || || 2 || 2 || || || 3 |
| || || || || X || || 1 |
| || || 6 || || || 7 || 7 |
| 5 || 4 || || X || || X || 1 |
| || 5 || || 6 || || || |

Output

Solution to the above table

| 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 |

Example

#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 - Gets a node and returns the set pointer. */

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</p><p>",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</p><p>",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</p><p>",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</p><p>",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</p><p>",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</p><p>",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</p><p>",stat);
            if(stat) {
               flag=1;
               break;
            }
         }
      }
      ct++;
   }
   //printf("flag- %d</p><p>",flag);
   if(flag==0)
      return -1;
   if(flag) {
      //printf("value sent- %d</p><p>", 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</p><p>",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:</p><p>");
   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("</p><p>");
   }
   printf("</p><p></p><p>The solution to the above table:</p><p>");
   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("</p><p>");
   }
}
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;
}

The above is the detailed content of A number-matching game?. For more information, please follow other related articles on the PHP Chinese website!