题解 - Vijos

2

sonicmisora LV 8 @ 2009-09-17 17:32:48

数独最权威最快的算法还是DANCING LINKS X吧，的确挺快的，绝大部分数据都是秒杀。

1

搬运工 (syrth0p1) LV 10 @ 2026-02-20 14:07:23

参考https://www.luogu.com.cn/article/xpsongwb 修改

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mx 100100  // 保持原有大小，满足DLX的空间需求

// 全局变量改为局部，避免多组数据污染
struct DLX{
    int n,m,cnt;
    int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];
    int h[mx];
    int s[mx];
    int ansk[mx];
    
    void init(int _n,int _m){
        n=_n,m=_m;
        int i;
        for(i=0;i<=m;i++){
            r[i]=i+1;l[i]=i-1;u[i]=d[i]=i;
        }
        r[m]=0;
        l[0]=m;
        memset(h,-1,sizeof(h));
        memset(s,0,sizeof(s));
        cnt=m+1;
    }
    
    void link(int R,int C){
        s[C]++;
        row[cnt]=R;
        col[cnt]=C;
        u[cnt]=C;
        d[cnt]=d[C];
        u[d[C]]=cnt;
        d[C]=cnt;
        if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;
        else{
            r[cnt]=h[R];
            l[cnt]=l[h[R]];
            r[l[h[R]]]=cnt;
            l[h[R]]=cnt;
        }
        cnt++;
    }
    
    void remove(int c){
        r[l[c]]=r[c],l[r[c]]=l[c];
        for(int i=d[c];i!=c;i=d[i]){
            for(int j=r[i];j!=i;j=r[j]){
                u[d[j]]=u[j];
                d[u[j]]=d[j];
                s[col[j]]--;
            }
        }
    }
    
    void resume(int c){
        for(int i=u[c];i!=c;i=u[i]){
            for(int j=l[i];j!=i;j=l[j]){
                u[d[j]]=j;
                d[u[j]]=j;
                s[col[j]]++;
            }
        }
        r[l[c]]=c;
        l[r[c]]=c;
    }
    
    bool dance(int deep, int a[10][10]){  // 把数独数组作为参数传入
        if(r[0]==0){
            int x,y,v;
            for(int i=0;i<deep;i++){
                x=(ansk[i]-1)/9/9;
                y=(ansk[i]-1)/9%9;
                v=(ansk[i])%9;
                if(v==0)v=9;
                a[x][y]=v;
            }
            return 1;
        }
        int c=r[0];
        for(int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
        remove(c);
        for(int i=d[c];i!=c;i=d[i]){
            ansk[deep]=row[i];
            for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
            if(dance(deep+1,a)==1)return 1;
            for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
        }
        resume(c); 
        return false;
    }
}dlx;

// 处理单个数字串形式的数独
void solve_sudoku(const string& input_str) {
    int a[10][10];  // 局部数独数组，避免多组数据干扰
    int idx = 0;
    
    // 解析81位数字串到9x9的数独数组
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++){
            a[i][j] = input_str[idx++] - '0';  // 字符转数字
        }
    }
    
    // 初始化DLX并构建精确覆盖矩阵
    dlx.init(729, 324);
    int o;
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++){
            int x = a[i][j];
            for(int k=1;k<=9;k++){
                if(x!=k && x!=0) continue;
                o = i*9*9 + j*9 + k;
                dlx.link(o, i*9 + j + 1);
                dlx.link(o, i*9 + 81 + k);
                dlx.link(o, j*9 + 81*2 + k);
                dlx.link(o, 81*3 + (i/3*3 + j/3)*9 + k);
            }
        }
    }
    
    // 执行舞蹈链算法求解
    dlx.dance(0, a);
    
    // 输出81位结果串
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++){
            printf("%d", a[i][j]);  // 无空格输出
        }
    }
    printf("\n");  // 每组结果换行
}

int main(){
    int n;
    scanf("%d", &n);  // 读取数独个数
    getchar();  // 吃掉换行符，避免干扰后续字符串读取
    
    // 处理n个数独
    for(int i=0;i<n;i++){
        string s;
        getline(cin, s);  // 读取每行81位的数字串
        solve_sudoku(s);
    }
    
    return 0;
}

1

liuyiah LV 10 @ 2016-08-30 17:04:28

DLX算法真心BT。。
15ms出结果

1

NPC LV 8 @ 2014-08-06 22:29:25

#include<cstdio>
#include<cstring>
int n,a[10][10];
char s[100];
bool h[10][10],l[10][10],sq[10][10];

void Print();
void DFS(int x,int y);
int Getsq(int x,int y);

int main(){
freopen("p1345.in","r",stdin);
scanf("%d",&n);
for (int k=1;k<=n;k++){
memset(h,false,sizeof h);
memset(l,false,sizeof l);
memset(sq,false,sizeof sq);
scanf("%s",s);
for (int i=1;i<=9;i++){
for (int j=1;j<=9;j++) a[i][j]=s[(i-1)*9+j-1]-'0',h[i][a[i][j]]=l[j][a[i][j]]=true,sq[Getsq(i,j)][a[i][j]]=true;
}
DFS(1,1);
}
}

void DFS(int x,int y){
if (a[x][y]!=0){
if (x==9 && y==9) Print();
else if (y==9) DFS(x+1,1);
else DFS(x,y+1);
}
else
for (int num=1;num<=9;num++){
if (!sq[Getsq(x,y)][num] && !h[x][num] && !l[y][num]){
sq[Getsq(x,y)][num]=h[x][num]=l[y][num]=true;
a[x][y]=num;
if (x==9 && y==9) Print();
else if (y==9) DFS(x+1,1);
else DFS(x,y+1);
a[x][y]=0;
sq[Getsq(x,y)][num]=h[x][num]=l[y][num]=false;
}
}
}

int Getsq(int x,int y){
return (((x-1)/3)*3+(y-1)/3+1);
}

void Print(){
for (int i=1;i<=9;i++){
for (int j=1;j<=9;j++) printf("%d",a[i][j]);
}
printf("\n");
}

why WA? 求大神指点...

1

K-Boy LV 10 @ 2010-03-03 07:46:17

按列搜索是无比强大的！！！！

膜拜qjl神牛！！！！！！！！

1

blacksnow LV 10 @ 2009-11-03 21:34:35

如果你刚好easy...

连续N次EASY，看来人品“不错”！

1

Matt LV 10 @ 2009-10-02 11:09:38

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：960ms

位运算的胜利...

1

Arker LV 6 @ 2008-08-13 16:04:22

伟大的Dancing Link..

0

LSQ LV 8 @ 2010-04-07 21:27:23

不知道哪里错了，帮我看一下程序，谢谢

编译通过...

├ 测试数据 01：运行超时|格式错误...

├ 测试数据 02：答案错误...

　├ Hint: 程序问题多了。　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...

　├ Hint: 稍变态。　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：运行超时...

├ 测试数据 08：答案错误...

　├ Hint: 垃圾点。　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：运行超时...

├ 测试数据 10：答案错误...

　├ Hint: 极变态，过不了也没什么。　├ 标准行输出

　├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

type r=array[1..9,1..9] of byte;

var f:array[1..9,1..9,1..9,1..2] of integer;

n,i,j,k:integer;

ch:char;

a:r;

procedure search(x,y:integer);

var ii,jj:integer;

bool:boolean;

begin

if (x=9) and (y=9) then begin

for ii:=1 to 9 do

for jj:=1 to 9 do

write(a[ii,jj]);

writeln;

exit;

end else begin

inc(y);

if y=10 then begin x:=x+1; y:=1; end;

if a[x,y]0 then search(x,y) else begin

for ii:=1 to 9 do begin

bool:=true;

for jj:=1 to 9 do

if ii=a[f[x,y,jj,1],f[x,y,jj,2]] then bool:=false;

if bool=true then begin

for jj:=1 to 9 do

if (a[x,jj]=ii) or (a[jj,y]=ii) then bool:=false;

if bool=true then begin

a[x,y]:=ii;

search(x,y);

a[x,y]:=0;

end;

end;

end;

end;

end;

end;

begin

readln(n);

for i:=1 to 3 do

for j:=1 to 3 do begin

f:=1; f:=1; f:=1;

f:=1; f:=2; f:=3;

f:=2; f:=2; f:=2;

f:=1; f:=2; f:=3;

f:=3; f:=3; f:=3;

f:=1; f:=2; f:=3;

end;

for i:=1 to 3 do

for j:=4 to 6 do begin

f:=1; f:=1; f:=1;

f:=4; f:=5; f:=6;

f:=2; f:=2; f:=2;

f:=4; f:=5; f:=6;

f:=3; f:=3; f:=3;

f:=4; f:=5; f:=6;

end;

for i:=1 to 3 do

for j:=7 to 9 do begin

f:=1; f:=1; f:=1;

f:=7; f:=8; f:=9;

f:=2; f:=2; f:=2;

f:=7; f:=8; f:=9;

f:=3; f:=3; f:=3;

f:=7; f:=8; f:=9;

end;

for i:=4 to 6 do

for j:=1 to 3 do begin

f:=4; f:=5; f:=6;

f:=1; f:=2; f:=3;

f:=4; f:=5; f:=6;

f:=1; f:=2; f:=3;

f:=4; f:=5; f:=6;

f:=1; f:=2; f:=3;

end;

for i:=4 to 6 do

for j:=4 to 6 do begin

f:=4; f:=4; f:=4;

f:=4; f:=5; f:=6;

f:=5; f:=5; f:=5;

f:=4; f:=5; f:=6;

f:=6; f:=6; f:=6;

f:=4; f:=5; f:=6;

end;

for i:=4 to 6 do

for j:=7 to 9 do begin

f:=4; f:=4; f:=4;

f:=7; f:=8; f:=9;

f:=5; f:=5; f:=5;

f:=7; f:=8; f:=9;

f:=6; f:=6; f:=6;

f:=7; f:=8; f:=9;

end;

for i:=7 to 9 do

for j:=1 to 3 do begin

f:=7; f:=7; f:=7;

f:=1; f:=2; f:=3;

f:=8; f:=8; f:=8;

f:=1; f:=2; f:=3;

f:=9; f:=9; f:=9;

f:=1; f:=2; f:=3;

end;

for i:=7 to 9 do

for j:=4 to 6 do begin

f:=7; f:=7; f:=7;

f:=4; f:=5; f:=6;

f:=8; f:=8; f:=8;

f:=4; f:=5; f:=6;

f:=9; f:=9; f:=9;

f:=4; f:=5; f:=6;

end;

for i:=7 to 9 do

for j:=7 to 9 do begin

f:=7; f:=7; f:=7;

f:=7; f:=8; f:=9;

f:=8; f:=8; f:=8;

f:=7; f:=8; f:=9;

f:=9; f:=9; f:=9;

f:=7; f:=8; f:=9;

end;

for i:=1 to n do begin

fillchar(a,sizeof(a),0);

for j:=1 to 9 do

for k:=1 to 9 do begin

read(ch);

a[j,k]:=ord(ch)-48;

end;

search(0,9);

end;

end.

虽然有点长，但容易理解，谢谢

0

Jungle LV 10 @ 2009-09-14 11:54:25

第2点始终不过啊是不是有多解= =。。

某次网赛的数独题我贴我的90分程序都ac了= =

0

SHvsMKwyc LV 8 @ 2009-09-12 15:03:50

编译通过...

├ 测试数据 01：答案正确... 1541ms

├ 测试数据 02：答案正确... 150ms

├ 测试数据 03：答案正确... 744ms

├ 测试数据 04：答案正确... 291ms

├ 测试数据 05：答案正确... 7619ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 681ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 306ms

├ 测试数据 10：答案正确... 1416ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：12748ms

过了我几乎两天！！！搜索是在写得太丑了！！！交了近20次！！！悲哀ing！！！

爆搜确实能过！但只要有一个地方想差了，你就别想过了！下面是我认为最核心的部分！

const int MAXN=10;

int jgg[MAXN][MAXN]=

{{0,0,0,0,0,0,0,0,0,0},

{0,1,1,1,2,2,2,3,3,3},

{0,1,1,1,2,2,2,3,3,3},

{0,1,1,1,2,2,2,3,3,3},

{0,4,4,4,5,5,5,6,6,6},

{0,4,4,4,5,5,5,6,6,6},

{0,4,4,4,5,5,5,6,6,6},

{0,7,7,7,8,8,8,9,9,9},

{0,7,7,7,8,8,8,9,9,9},

{0,7,7,7,8,8,8,9,9,9}};

struct point

{

int x,y;

};

point wwg[82];

int num;

int a[MAXN][MAXN];

bool h[MAXN][MAXN],l[MAXN][MAXN],pj[MAXN][MAXN];

如果没有把这些定义好的话！我想一定会超！特别是jgg【】【】这个数组！！！太重要了！！！！

然后就是这个

if(pj[jgg[wwg[m].x][wwg[m].y]][i]==false)

if(h[wwg[m].x][i]==false)

if(l[wwg[m].y][i]==false)

这三个判断的顺序是关键！！！

改了顺序就能过变态的第五组数据啦！

虽说是搜索，细节决定成败！！！

0

oimaster LV 10 @ 2009-08-31 15:22:09

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

DLX算法的结果……

0

fp_ks LV 10 @ 2009-08-30 21:58:59

编译通过...

├ 测试数据 01：答案正确... 103ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 9ms

├ 测试数据 05：答案正确... 275ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 447ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：968ms

0

wzc1995 LV 10 @ 2009-08-30 16:58:25

编译通过...

├ 测试数据 01：答案正确... 1244ms

├ 测试数据 02：答案正确... 134ms

├ 测试数据 03：答案正确... 634ms

├ 测试数据 04：答案正确... 212ms

├ 测试数据 05：答案正确... 5947ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 666ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 291ms

├ 测试数据 10：答案正确... 1322ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：10450ms

部分评测机会挂

核心部分：

int search(int i,int j)

{

if(table[i][j]>0)

{

if(i==8&&j==8)

return 1;

int result;

if(j==8)

result=search(i+1,0);

else

result=search(i,j+1);

return result;

}

else

{

for(int cur=1;cur

0

kekeczxa LV 10 @ 2009-08-18 10:51:09

vj抽了。。换行全不见了

0

zhujf553 LV 10 @ 2009-08-06 14:36:58

编译通过...

├ 测试数据 01：答案正确... 2212ms

├ 测试数据 02：答案正确... 478ms

├ 测试数据 03：答案正确... 619ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 775ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 666ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4894ms

按列搜索很快啊

0

qjl LV 9 @ 2009-08-05 12:27:07

我用的深搜，不过时间上有点囧。

第一次，搜索顺序先行后列（即1,1-->1,9-->2,1-->……-->9,9）：

编译通过...

├ 测试数据 01：答案正确... 1603ms

├ 测试数据 02：答案正确... 181ms

├ 测试数据 03：答案正确... 853ms

├ 测试数据 04：答案正确... 306ms

├ 测试数据 05：运行超时|无输出...

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行超时...

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 400ms

├ 测试数据 10：答案正确... 1556ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：75 有效耗时：4908ms

第二次，搜索顺序先列后行（即1,1-->9,1-->1,2-->……-->9,9）：编译通过...

├ 测试数据 01：答案正确... 2181ms

├ 测试数据 02：答案正确... 462ms

├ 测试数据 03：答案正确... 634ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 759ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 728ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4924ms

我最感兴趣的是第一次提交时，我只错了两个点，却扣了25分？有意思。

0

ljq LV 10 @ 2009-08-04 12:40:32

编译通过...

├ 测试数据 01：答案正确... 2119ms

├ 测试数据 02：答案正确... 478ms

├ 测试数据 03：答案正确... 634ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 791ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 712ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4878ms

膜拜秒杀的大牛！！！

0

fammiebright LV 9 @ 2009-07-28 18:41:19

编译通过...

├ 测试数据 01：答案正确... 1447ms

├ 测试数据 02：答案正确... 119ms

├ 测试数据 03：答案正确... 775ms

├ 测试数据 04：答案正确... 259ms

├ 测试数据 05：答案正确... 6822ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 759ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 338ms

├ 测试数据 10：答案正确... 1400ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：11919m

纯朴素dfs。

0

NaTuReHugh LV 9 @ 2009-07-24 12:14:33

编译通过...

├ 测试数据 01：答案正确... 1056ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 572ms

├ 测试数据 04：答案正确... 150ms

├ 测试数据 05：答案正确... 712ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 197ms

├ 测试数据 09：答案正确... 572ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3450ms

正着搜索95分，倒着95分，最后干脆根据N尽心随即正反，就AC了，汗

题解

68 条题解

数独大赛

信息

状态

开发

支持

题解

68 条题解

数独大赛

信息

状态

开发

支持

还没有账户？

登录