एक नंबर लिंक गेम?

नंबर लिंक एक प्रकार का तर्क पहेली है जिसमें ग्रिड में संख्याओं को जोड़ने के लिए पथ ढूंढना शामिल है।

नंबरलिंक पहेली का एक सरल उदाहरण - नंबरलिंक पहेली का समाधान

नियम - खिलाड़ी को ग्रिड पर मिलान करने वाली सभी संख्याओं को एकल निरंतर रेखाओं (या पथों) के साथ जोड़ना होगा। रेखाएं शाखा नहीं बना सकतीं या एक-दूसरे को पार नहीं कर सकतीं, और संख्याओं को प्रत्येक रेखा के अंत में होना चाहिए (यानी, बीच में नहीं)। यह माना जाता है कि एक समस्या तभी अच्छी तरह से डिज़ाइन की गई है जब इसका एक अद्वितीय समाधान हो और ग्रिड में सभी सेल भरे हों, हालांकि कुछ नंबरलिंक डिजाइनर इस शर्त को नहीं रखते।

गेम - 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) अब तक उत्पन्न किसी पथ से संबंधित है। यदि पूरे बोर्ड पर ऐसा कोई वर्ग युग्म नहीं मिलता है, तो FAILURE लौटाएं /* यहां, (i, j) और (k, l) नए पथ पर बनने वाले पहले दो वर्ग हैं। *

• (i, j) और (k, l) वाले दो यूनियन-फाइंड ट्री का यूनियन बनाएं।

• इतनी देर दोहराएं जब तक वर्तमान पथ बढ़ाया जा सकता है: (i, j) का नाम बदलकर (k, l) करें। (i, j) के एक रैंडम पड़ोसी वर्ग (k, l) का पता लगाएं जैसे कि: (a) (k, l) अब तक उत्पन्न किसी पथ से संबंधित नहीं है (वर्तमान सहित) (b) (k, l) का आंशिक रूप से निर्मित वर्तमान पथ पर एकमात्र पड़ोसी (i, j) है।

• यदि ऐसा कोई पड़ोसी (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;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
Description - Takes 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 && 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); 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); 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); 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); 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); 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); 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); if(stat) { flag=1; break; } } } ct++;
    }
    if(flag==0) return -1;
    if(flag) { 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) // शुरू करने के लिए कोई वैध युग्म नहीं मिला
        return 0;
    k1= k2/(n*n);
    k2= k2%(n*n);
    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;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("\n");
    }
    printf("\n\nThe solution to the above table:\n");
    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("\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