Trò chơi Number Link

Number Link là trò chơi logic tìm đường nối các số trên lưới.

Ví dụ đơn giản của Number Link. Lời giải:

Luật chơi - Người chơi phải nối các cặp số trùng khớp trên lưới bằng đường liên tục đơn. Đường không được rẽ nhánh hoặc cắt nhau, số phải ở cuối đường (không ở giữa). Coi như bài toán tốt nếu có lời giải duy nhất và tất cả ô được lấp đầy.

Trò chơi - Xét mảng n×n. Một số ô trống, một số ô rắn, một số ô không rắn được gán số nguyên 1, 2, 3... Mỗi số chiếm đúng hai ô khác nhau. Nhiệm vụ: nối hai lần xuất hiện của mỗi số bằng đường đơn giản chỉ dùng di chuyển ngang/dọc. Hai đường khác nhau không được cắt nhau. Đường không được đi qua ô rắn. Cuối cùng, tất cả ô không rắn phải được lấp đầy bởi các đường.

Thuật toán - Để tạo bài toán ngẫu nhiên hợp lệ kích thước n×n, trước tạo các đường đơn ngẫu nhiên không cắt nhau trên bàn cờ. Nếu còn ô đơn lẻ ngoài các đường, đánh dấu chúng là rắn (cấm). Sau đó cung cấp các đầu đường và danh sách ô rắn làm bài toán.

Vậy ta tạo lời giải trước, rồi ra bài toán từ lời giải. Các đường và ô rắn phân hoạch bàn cờ n×n. Dùng cấu trúc dữ liệu union-find để tạo phân hoạch này. Cấu trúc này xử lý các tập con của tập n^2 ô trên bàn cờ.

Giải thích

• Tìm ô (i, j) và (k, l) ngẫu nhiên trên bàn cờ sao cho: (a) chúng là hàng xóm, (b) không thuộc đường nào đã tạo. Nếu không tìm thấy cặp nào, trả về THẤT BÁI.
• Hợp nhất hai cây union-find chứa (i, j) và (k, l).
• Lặp lại miễn là đường hiện tại có thể mở rộng: Đổi tên (i, j) = (k, l). Tìm ô hàng xóm ngẫu nhiên (k, l) của (i, j) sao cho: (a) (k, l) không thuộc đường nào đã tạo (kể cả đường hiện tại), (b) hàng xóm duy nhất của (k, l) trên đường đang xây là (i, j).
• Nếu không tìm thấy hàng xóm (k, l), đường không mở rộng được, thoát vòng lặp.
• Ngược lại, hợp nhất hai cây union-find chứa (i, j) và (k, l).
• Đặt cờ đầu cuối cho hai ô ở đầu và cuối đường mới.
• Trả về THÀNH CÔNG.

Đầu vào

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

Đầu ra

Lời giải của bảng trên

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

Ví dụ

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

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) {
    // ... (code dài, xem nguồn gốc)
}

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