เกมเชื่อมโยงตัวเลข?

ลิงก์ตัวเลขเป็นปริศนาประเภทหนึ่งที่เกี่ยวข้องกับการค้นหาเส้นทางเพื่อเชื่อมต่อตัวเลขในตาราง

ตัวอย่างง่ายๆ ของปริศนา Numberlink วิธีแก้ปริศนา Numberlink

กฎ − ผู้เล่นต้องจับคู่ตัวเลขที่ตรงกันทั้งหมดในตารางด้วยบรรทัดเดียว (หรือเส้นทาง) ที่ต่อเนื่องกัน เส้นไม่สามารถแตกแขนงหรือตัดกัน และตัวเลขต้องอยู่ท้ายแถวแต่ละเส้น (เช่น ไม่อยู่ตรงกลาง) ถือว่าปัญหาได้รับการออกแบบมาอย่างดีก็ต่อเมื่อมีวิธีแก้ปัญหาที่ไม่ซ้ำกันและเซลล์ทั้งหมดในตารางถูกเติม แม้ว่านักออกแบบ Numberlink บางคนจะไม่กำหนดสิ่งนี้

เกม − พิจารณาอาร์เรย์ n × n ของช่องสี่เหลี่ยม สี่เหลี่ยมจัตุรัสบางอันว่างเปล่า บางอันเป็นทรงทึบ และสี่เหลี่ยมจัตุรัสที่ไม่ทึบบางอันทำเครื่องหมายด้วยจำนวนเต็ม 1, 2, 3, … แต่ละจำนวนเต็มใช้พื้นที่สองช่องที่แตกต่างกันบนกระดาน งานของผู้เล่นคือการเชื่อมต่อทั้งสองเหตุการณ์ของจำนวนเต็มแต่ละจำนวนบนกระดานโดยใช้เส้นทางง่ายๆ โดยใช้การเคลื่อนที่ในแนวนอนและแนวตั้งเพียงอย่างเดียว ไม่อนุญาตให้มีเส้นทางที่แตกต่างกันสองทางมาบรรจบกัน ไม่มีเส้นทางใดที่อาจรวมถึงสี่เหลี่ยมทึบ (สี่เหลี่ยมทึบถูกห้ามไม่ให้ปรากฏบนเส้นทางใด ๆ ) สุดท้าย ต้องเติมช่องสี่เหลี่ยมที่ไม่ทึบทั้งหมดด้วยเส้นทาง

อัลกอริทึม − ในการเตรียมปริศนาตัวต่อแบบสุ่มที่ถูกต้องด้วยขนาดกระดานที่กำหนด n × n ขั้นแรกเราจะสร้างเส้นทางธรรมดาที่ไม่ตัดกันบนกระดานอย่างง่าย หากสี่เหลี่ยมแยกบางส่วนยังคงอยู่นอกเส้นทางที่สร้างขึ้นทั้งหมด ให้ทำเครื่องหมายสี่เหลี่ยมแยกเหล่านี้เป็นทึบ (ต้องห้าม) จากนั้นเราจะจัดหาจุดสิ้นสุดของเส้นทางและรายการสี่เหลี่ยมทึบเป็นปริศนา

ดังนั้นเราจึงสร้างวิธีแก้ปัญหาก่อนแล้วจึงไขปริศนาจากวิธีแก้ปัญหา เส้นทางและสี่เหลี่ยมทึบแบ่งกระดาน n × n เราใช้โครงสร้างข้อมูล union-find เพื่อสร้างพาร์ติชันนี้ โครงสร้างข้อมูลเกี่ยวข้องกับเซตย่อยของเซต n^2 สี่เหลี่ยมบนกระดาน

คำอธิบาย

• ค้นหาช่องสี่เหลี่ยม (i, j) และ (k, l) แบบสุ่มบนกระดานเพื่อให้:(a) (i, j) และ (k, l) เป็นเพื่อนบ้านของกันและกันและ (b) ไม่ใช่ (i, j) nor (k, l) เป็นของเส้นทางใด ๆ ที่สร้างขึ้นจนถึงตอนนี้ หากไม่พบสี่เหลี่ยมคู่ดังกล่าวในกระดานทั้งหมด ให้ส่งคืน FAILURE /* ที่นี่ (i, j) และ (k, l) เป็นสองช่องแรกบนเส้นทางใหม่ที่จะสร้าง *

• สร้างการรวมตัวของต้นไม้สองต้นที่มี (i, j) และ (k, l)

• ทำซ้ำตราบเท่าที่เส้นทางปัจจุบันสามารถขยายได้:เปลี่ยนชื่อ (i, j) =(k, l) ค้นหาสี่เหลี่ยมข้างเคียงแบบสุ่ม (k, l) ของ (i, j) ในลักษณะที่ว่า:(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\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;
}