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中部&京都賞楓】Day 3 京都 南禪寺

2024-11-29   帶著滿滿感動走出永觀堂，順路走到南禪寺。南禪寺歷史落落長，就不贅述了。總之是日本最早由皇室發願建造的勅願

2024-12-27

我也來寫日記1131227

--------------------------------------- 〈我也來寫日記1131227〉        昨天和今天我都要出差，不同

2024-12-27

大摩2025年十大意外 美元貶值居首

https://m.hkej.com/landing/mobarticle2/id/3963076/%25E5%25A4%25A7%25E6%2591%25A92025%25E5%25B9%25B4%25E5%258D%2581%25E5%25A4

3 小時前

厭倦

不滿的情緒已高漲，該有所決定了... 只是自己都覺得好笑，以為說服了某人該退休了，結果是自己滾蛋... 也罷！為了生存，所有的

8 小時前

小說集『夏のカレー』

看到書腰的陣容，不難猜出我為什麼會買下這本短篇小說集《夏のカレー》（夏日咖哩）。 沒錯，有小川哲又有宮島未奈，要我怎麼錯過

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

PChome Online and PChome are trademarks of PChome Online Inc.