poj 3074 Sudoku(DX解9*9数独)


->タイトルはここを押してください.
9*9数独を記入すると、余計なことを言わなくなります.
題目の分析:以前は数独を書いて検索で作ったもので、やや暴力的に列挙しています.コードの量が多く、効率も高くないです.最近はdancing linksを勉強して、正確なカバー問題を解決します.数独が正確なカバー問題に転化したことについて、この論文の話はとても詳しくて、ここのクラスで斧をいじりませんでした.詳細はコードをご覧ください.
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 9 * 9 * 9 * 9 * 9 * 4 + 5;//9 * 9 * 9 9 * 9 * 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[200];

void init()
{
    memset(s,0,sizeof(s));//     ,  TLE!!
    head = 0;
    int i;
    int c = 9 * 9 * 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)
    {
        sort(ans,ans + 81);
        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() { while(scanf("%s",str) != EOF) { if(str[0] == 'e') break; init(); //system("pause"); for(int i = 0;i < strlen(str);i ++) { int rr = i / 9; int cc = i - rr * 9; int base = (rr * 9 + cc) * 9; if(str[i] == '.') { for(int k = 1;k <= 9;k ++)// 1-9 { insert(base + k,rr * 9 + k);// rr k insert(base + k,81 + 9 * cc + k);// cc k insert(base + k,81 + 81 + (3 * (rr / 3) + cc / 3) * 9 + k); insert(base + k,81 + 81 + 81 + rr * 9 + cc + 1); } } else { insert(base + str[i] - '0',rr * 9 + str[i] - '0'); insert(base + str[i] - '0',81 + 9 * cc + str[i] - '0'); insert(base + str[i] - '0',81 + 81 + (3 * (rr / 3) + cc / 3) * 9 + str[i] - '0'); insert(base + str[i] - '0',81 + 81 + 81 + rr * 9 + cc + 1); } } dfs(0); } return 0; } //7568K 375MS