poj 3076 Sudoku(私の大DL威武!16*16数独秒解!!!)

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 16 * 16 * 16 * 16 * 16 * 4 + 5;//16 * 16 * 16 16 * 16 * 4 
int s[N],h[N],u[N],d[N],l[N],r[N],col[N],row[N],ans[N];
int head,num;
char str[20][20];

void init()
{
    memset(s,0,sizeof(s));//     ，  TLE！！
    head = 0;
    int i;
    int c = 16 * 16 * 4;
    for(i = 0;i <= c;i ++)
    {
        u[i] = d[i] = i;
        l[i] = (i - 1 + c + 1) % (c + 1);
        r[i] = (i + 1) % (c + 1);
    }
    num = c + 1;
    memset(h,0,sizeof(h));

}

void insert(int i,int j)
{
    if(h[i])
    {
        r[num] = h[i];
        l[num] = l[h[i]];
        l[r[num]] = num;
        r[l[num]] = num;
    }
    else
    {
        h[i] = num;
        l[num] = r[num] = num;
    }
    s[j] ++;
    u[num] = u[j];
    d[num] = j;
    d[u[j]] = num;
    u[j] = num;
    col[num] = j;
    row[num] = i;
    num ++;
}

void del(int c)
{
    l[r[c]] = l[c];
    r[l[c]] = r[c];
    int i,j;
    for(i = d[c];i != c;i = d[i])
    {
        for(j = r[i];j != i;j = r[j])
        {
            u[d[j]] = u[j];
            d[u[j]] = d[j];
            s[col[j]] --;
        }
    }
}

void recover(int c)
{
    int i,j;
    for(i = u[c];i != c;i = u[i])
    {
        for(j = l[i];j != i;j = l[j])
        {
            s[col[j]] ++;
            u[d[j]] = d[u[j]] = j;
        }
    }
    r[l[c]] = l[r[c]] = c;
}

bool dfs(int k)
{
    int i,j;
    if(r[head] == head)
    {
        int t = 0;
        sort(ans,ans + 16 * 16);
        for(i = 0;i < 16;i ++)
        {
            for(j = 0;j < 16;j ++)
            {
                printf("%c",ans[t ++] - 16 * (i * 16 + j) + 64);
            }
            printf("
");
        }
        //for(i = 0;i < 81;i ++)
        //{
        //    printf("%d",ans[i] - i * 9);
       // }
        printf("
");
        return true;
    }
    int mn = N;
    int c;
    for(i = r[head];i != head;i = r[i])
    {
        if(s[i] < mn)
        {
            mn = s[i];
            c = i;
        }
    }
    del(c);
    for(i = d[c];i != c;i = d[i])
    {
        ans[k] = row[i];
        for(j = r[i];j != i;j = r[j])
            del(col[j]);
        if(dfs(k + 1))
            return true;
        for(j = l[i];j != i;j = l[j])
            recover(col[j]);
    }
    recover(c);
    return false;
}

int main()
{
    int i,j;
    while(scanf("%s",str[0]) != EOF)
    {
        for(i = 1;i < 16;i ++)
            scanf("%s",str[i]);
        init();
        //system("pause");
        for(i = 0;i < 16;i ++)
        {
            for(j = 0;j < 16;j ++)
            {
                int base = (i * 16 + j) * 16;
                if(str[i][j] == '-')
                {
                    for(int k = 1;k <= 16;k ++)//    1-16
                    {
                        insert(base + k,i * 16 + k);// i  k
                        insert(base + k,256 + 16 * j + k);// j  k
                        insert(base + k,256 + 256 + (4 * (i / 4) + j / 4) * 16 + k);
                        insert(base + k,256 + 256 + 256 + i * 16 + j + 1);
                    }
                }
                else
                {
                    insert(base + str[i][j] - 64,i * 16 + str[i][j] - 64);
                    insert(base + str[i][j] - 64,256 + 16 * j + str[i][j] - 64);
                    insert(base + str[i][j] - 64,256 + 256 + (4 * (i / 4) + j / 4) * 16 + str[i][j] - 64);
                    insert(base + str[i][j] - 64,256 + 256 + 256 + i * 16 + j + 1);
                }
            }
        }
        dfs(0);
    }
    return 0;
}