Morris' Blog

2011-08-13 07:29:10Morris

目前世界最快－解數獨的程序, 個人實作

留言 0 收藏 0 推薦 0
數據結構 : Dancing Links
將數獨盤面, 轉成矩陣, 變成了一個精準覆蓋問題,
要控制的有
1.該盤面存在的位置 (1~81 位置填上 1)
2.每一行, 所在的 1~9 ( 82~162 位置填上 1, 9 行中, 它填哪一行, 填什麼數字)
3.每一列, 所在的 1~9 (163~243 位置填上 1, 9 列中, 它填哪一列, 填什麼數字)
4.每一個方格, 所在的 1~9 (244~324位置填上 1)
因此, 每一格可能的解, 將由 4 個元素為 1 的控制

×　個人實作, 優化可能還做得不好, 可能還有所缺漏

範例輸入 :
3
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0
3
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 0 0 1 0 0 0 4
0 0 0 6 7 0 0 9 0
0 0 4 0 0 5 6 0 0
0 1 0 0 4 9 0 0 0
7 0 0 0 9 0 2 0 0
3 0 0 2 0 0 0 4 0
0 2 0 0 0 8 5 0 0
範例輸出 :
==================
9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3
TOTAL SOLUTION : 1
==================
1 5 3 9 8 4 7 6 2
2 4 7 5 3 6 1 8 9
6 9 8 7 1 2 3 5 4
8 3 2 6 7 1 4 9 5
9 7 4 8 2 5 6 3 1
5 1 6 3 4 9 8 2 7
7 6 5 4 9 3 2 1 8
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
2 4 7 5 3 6 1 8 9
6 9 8 7 1 2 3 5 4
8 3 2 6 7 1 4 9 5
9 7 4 8 2 5 6 3 1
5 1 6 3 4 9 8 2 7
7 8 5 4 9 3 2 1 6
3 6 1 2 5 7 9 4 8
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
2 4 8 7 3 6 1 5 9
6 9 7 5 1 2 3 8 4
8 3 2 6 7 1 4 9 5
9 7 4 8 2 5 6 3 1
5 1 6 3 4 9 8 2 7
7 6 5 4 9 3 2 1 8
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
2 4 8 7 3 6 1 5 9
6 9 7 5 1 2 3 8 4
8 3 2 6 7 1 4 9 5
9 7 4 8 2 5 6 3 1
5 1 6 3 4 9 8 2 7
7 8 5 4 9 3 2 1 6
3 6 1 2 5 7 9 4 8
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
2 4 8 7 3 6 1 5 9
6 9 7 5 1 2 8 3 4
8 3 2 6 7 1 4 9 5
9 7 4 3 2 5 6 1 8
5 1 6 8 4 9 3 2 7
7 6 5 4 9 3 2 8 1
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
2 4 8 7 3 6 1 5 9
6 9 7 5 1 2 8 3 4
8 3 2 6 7 1 4 9 5
9 7 4 3 2 5 6 8 1
5 1 6 8 4 9 3 2 7
7 6 5 4 9 3 2 1 8
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
2 4 8 7 3 6 1 5 9
6 9 7 5 1 2 8 3 4
8 3 2 6 7 1 4 9 5
9 7 4 3 2 5 6 8 1
5 1 6 8 4 9 3 2 7
7 8 5 4 9 3 2 1 6
3 6 1 2 5 7 9 4 8
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
8 4 2 7 3 6 1 5 9
6 9 7 5 1 2 3 8 4
2 3 8 6 7 1 4 9 5
9 7 4 8 2 5 6 3 1
5 1 6 3 4 9 8 2 7
7 6 5 4 9 3 2 1 8
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
8 4 2 7 3 6 1 5 9
6 9 7 5 1 2 3 8 4
2 3 8 6 7 1 4 9 5
9 7 4 8 2 5 6 3 1
5 1 6 3 4 9 8 2 7
7 8 5 4 9 3 2 1 6
3 6 1 2 5 7 9 4 8
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
8 4 2 7 3 6 1 5 9
6 9 7 5 1 2 8 3 4
2 3 8 6 7 1 4 9 5
9 7 4 3 2 5 6 1 8
5 1 6 8 4 9 3 2 7
7 6 5 4 9 3 2 8 1
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
8 4 2 7 3 6 1 5 9
6 9 7 5 1 2 8 3 4
2 3 8 6 7 1 4 9 5
9 7 4 3 2 5 6 8 1
5 1 6 8 4 9 3 2 7
7 6 5 4 9 3 2 1 8
3 8 1 2 5 7 9 4 6
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
8 4 2 7 3 6 1 5 9
6 9 7 5 1 2 8 3 4
2 3 8 6 7 1 4 9 5
9 7 4 3 2 5 6 8 1
5 1 6 8 4 9 3 2 7
7 8 5 4 9 3 2 1 6
3 6 1 2 5 7 9 4 8
4 2 9 1 6 8 5 7 3
==================
1 5 3 9 8 4 7 6 2
8 4 7 5 2 6 1 3 9
6 9 2 7 1 3 8 5 4
5 3 8 6 7 2 4 9 1
9 7 4 1 3 5 6 2 8
2 1 6 8 4 9 3 7 5
7 6 5 4 9 1 2 8 3
3 8 1 2 5 7 9 4 6
4 2 9 3 6 8 5 1 7
TOTAL SOLUTION : 13

/************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Maxv 100000
struct DacingLinks {
    int left, right;
    int up, down;
    int data, ch, rh;
}DL[100001 + 1001];
int s[1001], o[1001], head, size, time;
int n, m, a, b, c, tn;
void Remove(int c) {
    DL[DL[c].right].left = DL[c].left;
    DL[DL[c].left].right = DL[c].right;
    int i, j;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        for(j = DL[i].right; j != i; j = DL[j].right) {
            DL[DL[j].down].up = DL[j].up;
            DL[DL[j].up].down = DL[j].down;
            s[DL[j].ch]--;
        }
    }
}
void Resume(int c) {
    int i, j;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        for(j = DL[i].left; j != i; j = DL[j].left) {
            DL[DL[j].down].up = j;
            DL[DL[j].up].down = j;
            s[DL[j].ch]++;
        }
    }
    DL[DL[c].right].left = c;
    DL[DL[c].left].right = c;
}
void Print_board(int k) {
    static int set[81], a, b;
    for(a = 0; a < n; a++)
        printf("==");
    puts("");
    for(a = 0; a < k; a++) {
        set[DL[o[a]].data] = DL[o[a]].rh+1;
    }
    for(a = 0; a < n; a++) {
        for(b = 0; b < n; b++) {
            printf("%d ", set[a*9+b]);
        }
        puts("");
    }
}
void DFS(int k) {
    if(time > 10000000) return ;
    if(DL[head].right == head) {
        Print_board(k);
        time++;
        return;
    }
    int t = Maxv, c, i, j;
    for(i = DL[head].right; i != head; i = DL[i].right) {
        if(s[i] < t) {
            t = s[i], c = i;
        }
    }
    Remove(c);
    for(i = DL[c].down; i != c; i = DL[i].down) {
        o[k] = i;
        for(j = DL[i].right; j != i; j = DL[j].right)
            Remove(DL[j].ch);
        DFS(k+1);
        for(j = DL[i].left; j != i; j = DL[j].left)
            Resume(DL[j].ch);
    }
    Resume(c);
}
int new_node(int up, int down, int left, int right) {
    DL[size].up = up, DL[size].down = down;
    DL[size].left = left, DL[size].right = right;
    DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
    return size++;
}
void new_row(int n, int Row[], int rh, int set) {
    int a, r, row = -1, k;
    for(a = 0; a < n; a++) {
        r = Row[a];
        DL[size].ch = r, DL[size].data = set, s[r]++;
        if(row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
            DL[row].rh = rh;
        }else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
            DL[k].rh = rh;
        }
    }
}
void init(int m) {
    size = 0;
    head = new_node(0, 0, 0, 0);
    int i;
    for(i = 1; i <= m; i++) {
        new_node(i, i, DL[head].left, head);
        DL[i].ch = i, s[i] = 0;
    }
}
main() {
    int map[10][10], Row[10], t;
    while(scanf("%d", &n) == 1) {
        tn = n, n *= n, m = n*n*4, init(m);
        for(a = 0; a < n; a++)
            for(b = 0; b < n; b++) {
                scanf("%d", &map[a][b]);
                if(map[a][b] == 0) {
                    for(c = 0; c < n; c++) {
                        t = 0;
                        Row[t++] = a*n + b + 1;
                        Row[t++] = n*n + a*n + c + 1;
                        Row[t++] = 2*n*n+ b*n + c + 1;
                        Row[t++] = 3*n*n+ (a/tn*tn + b/tn)*n + c + 1;
                        new_row(t, Row, c, a*n+b);
                        /*printf("%d ", a*9 + b + 1);/*原始牌面上的標記
                        printf("%d ", 81 + a*9 + c + 1);/*行上1~9的標記
                        printf("%d ", 162+ b*9 + c + 1);/*列上1~9的標記
                        printf("%d ", 243+ (a/3*3 + b/3)*9 + c + 1);/*方格中1~9的標記
                        puts("");*/
                    }
                } else {
                    c = map[a][b]-1, t = 0;
                    Row[t++] = a*n + b + 1;
                    Row[t++] = n*n + a*n + c + 1;
                    Row[t++] = 2*n*n+ b*n + c + 1;
                    Row[t++] = 3*n*n+ (a/tn*tn + b/tn)*n + c + 1;
                    new_row(t, Row, c, a*n+b);
                    /*printf("%d ", a*9 + b + 1);/*原始牌面上的標記
                    printf("%d ", 81 + a*9 + c + 1);/*行上1~9的標記
                    printf("%d ", 162+ b*9 + c + 1);/*列上1~9的標記
                    printf("%d ", 243+ (a/3*3 + b/3)*9 + c + 1);/*方格中1~9的標記
                    puts("");*/
                }
            }
        time = 0, DFS(0);
        if(time)    printf("TOTAL SOLUTION : %d\n", time);
        else    puts("NO SOLUTION");
    }
    return 0;
}
/*
3
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0

3
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 0 0 1 0 0 0 4
0 0 0 6 7 0 0 9 0
0 0 4 0 0 5 6 0 0
0 1 0 0 4 9 0 0 0
7 0 0 0 9 0 2 0 0
3 0 0 2 0 0 0 4 0
0 2 0 0 0 8 5 0 0


9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3
*/

上一篇：[手動][大數][三角函數] sin x 運算

下一篇：[中興資工][程設][作業HW13]

你可能感興趣的文章

種兩個月的紅千鳥朝顏開花了

今年我從五月開始 種了不少朝顏 在蝦皮發現有一種迷你型  感覺適合我的陽台 讓我眼睛為之一亮 那就是紅千鳥朝顏 它的描述如

2024-11-22

薯來飽111

薯條的驚奇四大超人 芋頭地瓜山藥馬鈴薯 原本各自明白上天降下的旨意 知道自己落到凡間的靈魂任務 認清自己的本性，壯大自己

10 小時前

第五關：第99天

21.836296,97.577741

2024-11-22

Choetech 氮化鎵 GaN 充電器系列 45W/140W｜iPhone 16 PD 極速快充、電力升級超有感！

Choetech｜充電無限 – 全球領先3C充電配件領導品牌 科技產品的進步，從智慧型手機到筆記型電腦，再到耳機與平板，多設備同時

9 小時前

2025年預定的演出

1月2(四) 14:10 新竹建功中學「不只是崑曲」校園推廣演出 〈湖樓〉〈遊園驚夢〉與 陳元鴻，陳美蘭，潘宜庭   精誠中學「

14 小時前
PChome首頁 線上購物 24h購物 書店 露天拍賣 比比昂代購
新聞 / 氣象 股市 個人新聞台 廣告刊登 加入聯播網 全球購物
買賣租屋 支付連 國際連 Pi 拍錢包 旅遊 服務中心
買車 旅行團 汽車險推薦 線上麻將 雜誌 星座命理 會員中心
一元簡訊 直播達人 數位憑證 企業簡訊
買網址 虛擬主機 企業郵件
廣告刊登 隱私權聲明
消費者保護 兒童網路安全
About PChome 投資人聯絡 徵才
著作權保護｜網路家庭版權所有、轉載必究 ‧Copyright PChome Online

PChome Online and PChome are trademarks of PChome Online Inc.