เกม Number Link (Numberlink Puzzle) และอัลกอริทึมสร้างปริศนา

Number Link เป็นปริศนาตรรกะที่ต้องหาเส้นทางเชื่อมตัวเลขที่เหมือนกันในกริด

ตัวอย่างปริศนา Number Link (ซ้าย) และคำตอบ (ขวา)

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

เกม - พิจารณาอาร์เรย์ n x n บางช่องว่าง บางช่องเป็นของแข็ง (Solid) บางช่องมีตัวเลข 1,2,3... แต่ละตัวเลขครอบครอง 2 ช่อง ผู้เล่นต้องเชื่อม 2 ช่องของตัวเลขแต่ละตัวด้วย Path แบบ Horizontal/Vertical เท่านั้น Path ต่างห้ามทับกัน ห้ามผ่านช่อง Solid ทุกช่องที่ไม่ใช่ Solid ต้องถูกเติมโดย Path

อัลกอริทึม - เพื่อสร้างปริศนาที่ถูกต้องขนาด n x n เราสร้าง Path แบบสุ่มที่ไม่ทับกันก่อน หากเหลือช่องเดี่ยว ให้ทำเป็น Solid จากนั้นนำ Endpoint ของ Path และรายการ Solid มาเป็นปริศนา

ดังนั้นเราสร้างคำตอบก่อน แล้วค่อยสร้างปริศนาจากคำตอบ Path และ Solid แบ่งพื้นที่ n x n ใช้ Union-Find Data Structure สร้าง Partition นี้

คำอธิบาย

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

• ทำ Union ของ Union-Find Tree ที่มี (i,j) และ (k,l)

• ทำซ้ำขยาย Path: ย้าย (i,j) = (k,l) หาเพื่อนบ้าน (k,l) ใหม่ที่ (a) ไม่อยู่ใน Path ใดๆ (b) เพื่อนบ้านเดียวใน Path ปัจจุบันคือ (i,j) เท่านั้น

• หากไม่เจอเพื่อนบ้าน หยุดลูป

• มิฉะนั้น Union Tree ของ (i,j) และ (k,l)

• ตั้ง Flag Endpoint ที่จุดเริ่มและจบของ Path ใหม่

• Return SUCCESS

Input

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

Output

คำตอบของตารางด้านบน

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

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

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 checkneigh(int k1, int k2, int n, node ***arr) {
    // ... (โค้ดยาว ตัดสรุป)
}
int valid_next(int k, int n, node ***arr) {
    // ... (โค้ดยาว ตัดสรุป)
}
int addpath(node ***arr, int n, int ptno) {
    // ... (โค้ดยาว ตัดสรุป)
}
void printtable(node ***arr, int 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