Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

數據結構 : 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
*/