নাম্বার লিংক হলো একটি লজিক পাজেল যেখানে একটি গ্রিডে সংখ্যাগুলো সংযোগ করার পাথ খুঁজে বের করতে হয়।
একটি সাধারণ নাম্বারলিংক পাজেলের উদাহরণ এবং এর সমাধান
নিয়ম − খেলোয়াকে গ্রিডের সব মিলে যাওয়া সংখ্যাগুলো একক רציף লাইন (বা পাথ) দিয়ে জোড়া দিতে হয়। লাইনগুলো শাখা বাঁড়াতে বা একে অপর ক্রস করতে পারবে না, এবং সংখ্যাগুলো প্রতিটি লাইন-এর শেষে থাকতে হবে (মাঝপথে নয়)। একটি সমস্যা ভালো ডিজাইন করা মনে হয় যদি এর ইউনিক সমাধান থাকে এবং গ্রিডের সব সেল পূরণ হয়, যদিও কিছু নাম্বারলিংক ডিজাইনার এই শর্ত মানেন না।
গেম − একটি n × n আকারের স্কোয়ার অ্যারে বিবেচনা করুন। কিছু স্কোয়ার খালি, কিছু স olid, এবং কিছু নন-স olid স্কোয়ার ১, ২, ৩, ... দিয়ে চিহ্নিত। প্রতিটি ইন্টিজার বোর্ডে ঠিক দুটি ভিন্ন স্কোয়ার ঘেরে। খেলোয়ার কাজ হলো বোর্ডে প্রতিটি ইন্টিজারের দুটি~Occurrence কে হরিজেন্টাল এবং ভার্টিক্যাল মুভমেন্ট দিয়ে একটি সিম্পল পাথ দিয়ে সংযোগ করা। দুটি ভিন্ন পাথ একে অপর ইন্টারসেক্ট করতে পারবে না। কোনো পাথ কোনো স olid স্কোয়ার অন্তর্ভুক্ত করতে পারবে না (স olid স্কোয়ার কোনো পাথেও আসতে পারবে না)। চূড়ান্তভাবে, সব নন-স olid স্কোয়ার পাথ দিয়ে পূরণ থাকতে হবে।
অ্যালগরিদম − একটি দেওয়া বোর্ড আকার n × n-এ একটি বৈধ র্যান্ডম পাজেল তৈরি করতে, আমরা প্রথমে বোর্ডে র্যান্ডম সিম্পল পারস্পরিক নন-ইন্টারসেক্টিং পাথ জেনারেট করি। যদি কিছু আইসোলেটেড স্কোয়ার সব জেনারেটেড পাথের বাইরে থাকে, তবে সেগুলোকে স olid (নিষিদ্ধ) হিসেবে চিহ্নিত করি। তারপর পাথগুলোর এন্ডপয়েন্ট এবং স olid স্কোয়ারগুলোর তালিকা পাজেল হিসেবে দিয়ে দেওয়া হয়।
এভাবে আমরা প্রথমে সমাধান জেনারেট করি এবং তারপর সমাধান থেকে পাজেল বের করি। পাথগুলো এবং স olid স্কোয়ারগুলো n × n বোর্ডকে পার্টিশন করে। আমরা এই পার্টিশন জেনারেট করতে ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার ব্যবহার করি। এই ডেটা স্ট্রাকচার বোর্ডের n² সংখ্যক স্কোয়ারের সাবসেটগুলোর সাথে কাজ করে।
ব্যাখ্যা
বোর্ডে (i, j) এবং (k, l) স্কোয়ার র্যান্ডমলি লোকেট করুন যেন: (a) (i, j) এবং (k, l) একে অপরের neighbour, এবং (b) (i, j) বা (k, l) ইতিমধ্যে জেনারেট করা কোনো পাথের অংশ নয়। যদি পুরো বোর্ডে এমন কোনো জোড়া না মilise, তবে FAILURE রিটার্ন করুন। এখানে (i, j) এবং (k, l) নতুন পাথের প্রথম দুটি স্কোয়ার।
(i, j) এবং (k, l) থাকা দুটি ইউনিয়ন-ফাইন্ড ট্রির ইউনিয়ন করুন।
যতক্ষণ কレেন্ট পাথ এক্সটেন্ড করা যায়, ততক্ষণ পুনরাবৃত্তি করুন: (i, j) = (k, l) রিনেম করুন। (i, j)-এর একটি র্যান্ডম neighbouring স্কোয়ার (k, l) লোকেট করুন যেন: (a) (k, l) ইতিমধ্যে জেনারেট করা কোনো পাথের অংশ নয় (বর্তমান পাথসহ) (b) (k, l)-এর একমাত্র neighbour বর্তমান আংশিক পাথে (i, j)।
যদি এমন কোনো neighbour (k, l) না মিলে, তবে পাথ আর এক্সটেন্ড করা যাবে না, তাই লুপ ব্রেক করুন।
অন্যথায়, (i, j) এবং (k, l) থাকা দুটি ইউনিয়ন-ফাইন্ড ট্রির ইউনিয়ন করুন।
নতুন পাথের শুরু এবং শেষে থাকা দুটি স্কোয়ারের এন্ডপয়েন্ট ফ্ল্যাগ সেট করুন।
SUCCESS রিটার্ন করুন।
ইনপুট
| || || || || || || 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; }
