Problem:2924 新建题解

Solution_ID:27727            C++搜索回溯

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<bits/stdc++.h>

using namespace std;

int a[10][10],b[10][10],c[10][10],d[10][4][4],e[10]={0,9,9,9,9,9,9,9,9,9};

//b【10】【10】储存某数字是否在某行出现过,c 【10】【10】储存列,d储存 某个九宫格,e储存剩余数的个数 

void search(int x,int y){

if(x==9&&y==9){//搜索到9 9时输出 

for(int i=1;i<=8;i++){

for(int j=1;j<=8;j++) cout<<a[i][j]<<" ";

cout<<a[i][9];

cout<<endl;

}

for(int i=1;i<=8;i++) cout<<a[9][i]<<" ";

a[9][9]=0;//因为到9 9就输出了结果,9 9不确定 有没有值,所以统一清零 

for(int i=1;i<=9;i++)

for(int j=1;j<=9;j++){

if(a[i][j]) e[a[i][j]]--;

else for(int i=1;i<=9;i++) if(e[i]) cout<<i;

}//找到未出现的某数输出 

}

if(!a[x][y]){

for(int k=1;k<=9;k++)

if(!b[k][x]&&!c[k][y]&&!d[k][(x-1)/3+1][(y-1)/3+1]){//判断是否可放 

a[x][y]=k;

b[k][x]=1;

c[k][y]=1;

d[k][(x-1)/3+1][(y-1)/3+1]=1;

if(y<9) search(x,y+1);

else search(x+1,1);

a[x][y]=0;

b[k][x]=0;

c[k][y]=0;

d[k][(x-1)/3+1][(y-1)/3+1]=0;//回溯 

}

}

else if(y<9) search(x,y+1);//搜索下一位置 

else search(x+1,1);//到行尾搜索下一行 

}


int main(){

for(int i=1;i<=9;i++)

for(int j=1;j<=9;j++){

cin>>a[i][j];

if(a[i][j]){

b[a[i][j]][i]=1;

c[a[i][j]][j]=1;

d[a[i][j]][(i-1)/3+1][(j-1)/3+1]=1;

}

}

search(1,1);

return 0;

}


by 57135 七月 10, 2017, 8:20 a.m.

Solution_ID:27343            震惊!芬兰数学家的谜题竟13ms

                   时间复杂度:Θ() 空间复杂度:Θ()

测试点#1.in  结果:<label>AC</label>    内存使用量:  256kB     时间使用量:  6ms     
测试点#2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 1ms
测试点#6.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 37ms
测试点#hard1.in 结果:<label>AC</label> 内存使用量: 128kB 时间使用量: 13ms
测试点#hard2.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 13ms
测试点#hard3.in 结果:<label>AC</label> 内存使用量: 256kB 时间使用量: 3ms
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i=l;i<=r;++i)
int a[9][9];
inline bool check(int x,int y,int e){
	FOR(i,0,8)if(a[x][i]==e&&i!=y)return 0;
	FOR(i,0,8)if(a[i][y]==e&&i!=x)return 0;
	for(int i=x/3*3;i<x/3*3+3;i++)
		for(int j=y/3*3;j<y/3*3+3;j++)
			if(a[i][j]==e&&i!=x&&j!=y)
				return 0;
	return 1;
}
void dfs(int z){
	if(z==81){
		FOR(i,0,8){
			FOR(j,0,8)cout<<a[i][j]<<" ";
			cout<<endl;
		}
		exit(0);
	}
	int x=z/9;
	int y=z%9;
	if(a[x][y])
		dfs(z+1);
	else{
		FOR(i,1,9)if(check(x,y,i))a[x][y]=i,dfs(z+1);
		a[x][y]=0;
	}	
}
int main(){
	FOR(i,0,8)FOR(j,0,8)cin>>a[i][j];
	dfs(0);
}


by 45271 六月 20, 2017, 10:54 p.m.

Solution_ID:27140            暴力

                   时间复杂度:Θ(hehe) 空间复杂度:Θ(hehe)

#include<bits/stdc++.h>
using namespace std;
int tx,ty,a[9][9];
bool h1[9][10],h2[9][10],h3[9][10];
int find(int x,int y){
 int k1=x/3,k2=y/3;
 return k1*3+k2;
}
void next(int x,int y){
 ty=y+1;
 tx=x;
 if(ty>8){
  ty=0;
  tx++;
 }
}
void change(int x,int y,int t){ 
    int k=find(x,y);
 a[x][y]=t;
 h1[x][t]=1;
 h2[y][t]=1;
 h3[k][t]=1;
}
void change2(int x,int y,int t){
 int k=find(x,y);
 a[x][y]=0;
 h1[x][t]=0;
 h2[y][t]=0;
 h3[k][t]=0;
}
void print(){
 for(int i=0;i<9;i++){
  for(int j=0;j<9;j++){
   cout<<a[i][j]<<' ';
  }
  cout<<endl;
 }
}
void dfs(int x,int y){
 int k=find(x,y);
 if(x>8) print();
 if(a[x][y]){
  next(x,y);
  dfs(tx,ty);
 }
 else{
  for(int i=1;i<=9;i++){
   if(!(h1[x][i]||h2[y][i]||h3[k][i])){
    change(x,y,i);
    next(x,y);
    dfs(tx,ty);
    change2(x,y,i); 
   }
  }
 }
}
int main(){
 memset(h1,0,sizeof(h1));
 memset(h2,0,sizeof(h2));
 memset(h3,0,sizeof(h3));
    for(int i=0;i<9;i++){
     for(int j=0;j<9;j++){
      cin>>a[i][j];
      if(a[i][j]){
       int k=find(i,j);
       change(i,j,a[i][j]);
   }
  }
 }
 dfs(0,0);
 return 0;
}


by 12392 六月 3, 2017, 7:13 p.m.

Solution_ID:24470            fc‘s

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<algorithm>
using namespace std;
int ditu[9][9]={0};
int zhen[9][9][10]={0};
const int bb[3][3][9]={{{0,1,2,9,10,11,18,19,20},{3,4,5,12,13,14,21,22,23},{6,7,8,15,16,17,24,25,26}},
{{27,28,29,36,37,38,45,46,47},{30,31,32,39,40,41,48,49,50},{33,34,35,42,43,44,51,52,53}},
{{54,55,56,63,64,65,72,73,74},{57,58,59,66,67,68,75,76,77},{60,61,62,69,70,71,78,79,80}}};
void hui(int x,int y,int t){
    	for(int i=0;i<9;i++){
    		int p=bb[x/3][y/3][i];
    		zhen[i][y][t]--;
    		zhen[x][i][t]--;
		    zhen[p/9][p%9][t]--;
    	}
}
void su(int x,int y,int t){
	    for(int i=0;i<9;i++){
    		int p=bb[x/3][y/3][i];
		    zhen[i][y][t]++;
    		zhen[x][i][t]++;
    		zhen[p/9][p%9][t]++;
	}
	    ditu[x][y]=0;
}
void dfs(int k){
    	if(k==81){
    		for(int i=0;i<9;i++){
    			    for(int j=0;j<9;j++)
    				        cout<<ditu[i][j]<<" ";
    			    cout<<endl;
    		    }   
		    exit(0);	
    	}
    	if(ditu[k/9][k%9]){dfs(k+1);return;}
    	for(int i=1;i<=9;i++){
		        if(zhen[k/9][k%9][i]==0){
        			    ditu[k/9][k%9]=i;
			            hui(k/9,k%9,i);
			            dfs(k+1);
			            su(k/9,k%9,i);
		        }
    	}
}
int main(){
	    for(int i=0;i<9;i++)
		        for(int j=0;j<9;j++){
			            cin>>ditu[i][j];
			            hui(i,j,ditu[i][j]);
        		}	
	        dfs(0);cout<<"none";
}

by 49989 一月 18, 2017, 9:08 a.m.

Solution_ID:23733            ZZY

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>
#include<cstring>
#include<cstdlib>
	int a[10][10];
	bool h[10][10],l[10][10],g[10][10];
void print()
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	exit(0);
}
void go(int x,int y)
{
	if(a[x][y]!=0)
	{
		if(x==9&&y==9) print();
		if(y==9) go(x+1,1); else go(x,y+1);
	}
	if(a[x][y]==0)
	{
		for(int i=1;i<=9;i++)
			if(h[x][i]&&l[y][i]&&g[(x-1)/3*3+(y-1)/3+1][i])
			{
				a[x][y]=i;
				h[x][i]=false;
				l[y][i]=false;
				g[(x-1)/3*3+(y-1)/3+1][i]=false;
				if(x==9&&y==9) print();
				if(y==9) go(x+1,1); else go(x,y+1);
				a[x][y]=0;
				h[x][i]=true;
				l[y][i]=true;
				g[(x-1)/3*3+(y-1)/3+1][i]=true;
			}
	}
}
int main()
{
	memset(h,true,sizeof(h));
	memset(l,true,sizeof(l));
	memset(g,true,sizeof(g));
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]>0)
			{
				h[i][a[i][j]]=false;
				l[j][a[i][j]]=false;
				g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=false;
			}
		}
	go(1,1);
}

by 49186 十一月 29, 2016, 1:15 p.m.

Solution_ID:23722            laowang代码

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>
#include<cstdlib>
#include<cstring>

int a[10][10];
bool hang[10][10];
bool lie[10][10];
bool gong[10][10];
bool tf=false;

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

void dfs(int x,int y)
{
    if(tf==true)return;
    if(a[x][y]!=0)
    {
        if(x==9 && y==9)pr();
        if(y==9)dfs(x+1,1);
        else dfs(x,y+1);
    }
    if(a[x][y]==0)
    {
        for(int i=1;i<=9;i++)
        {
            if(hang[x][i]==true && lie[y][i]==true && gong[(x-1)/3*3+(y-1)/3+1][i]==true)
            {
                hang[x][i]=false;
                lie[y][i]=false;
                gong[(x-1)/3*3+(y-1)/3+1][i]=false;
                a[x][y]=i;
                if(x==9 && y==9)pr();
                if(y==9)dfs(x+1,1);
                else dfs(x,y+1);
                a[x][y]=0;
                hang[x][i]=true;
                lie[y][i]=true;
                gong[(x-1)/3*3+(y-1)/3+1][i]=true;
            }
        }
    }
}

int main()
{
    memset(hang,true,sizeof(hang));
    memset(lie,true,sizeof(lie));
    memset(gong,true,sizeof(gong));
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]!=0)
            {
                hang[i][a[i][j]]=false;
                lie[j][a[i][j]]=false;
                gong[(i-1)/3*3+(j-1)/3+1][a[i][j]]=false;
            }
        }
    }
    dfs(1,1);
}


by 18390 十一月 28, 2016, 1:36 p.m.

Solution_ID:20136            大神说可以优化,但是我没用上。。

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int a[10][10],c[90][3],k=0;

int l[10][10],h[10][10],jg[10][10];

int pd(int x,int y)

{

  if(x<=3&&y<=3) return 1;

  if(x<=3&&y<=6) return 2;

  if(x<=3&&y<=9) return 3;

  if(x<=6&&y<=3) return 4;

  if(x<=6&&y<=6) return 5;

  if(x<=6&&y<=9) return 6;

  if(x<=9&&y<=3) return 7;

  if(x<=9&&y<=6) return 8;

  if(x<=9&&y<=9) return 9;

}

void print()

{

int i,j; 

  for(i=1;i<=9;i++)

  {

     for(j=1;j<=8;j++)

     cout<<a[i][j]<<' ';

     cout<<a[i][9];

     cout<<endl;

  }

}

void search(int t)

{

   int i,x,y,p;

  x=c[t][1];

  y=c[t][2];

  p=pd(x,y);

  

   for(i=1;i<=9;i++)

  {

  if(l[y][i]==0&&h[x][i]==0&&jg[p][i]==0)

  {

  a[x][y]=i;

  l[y][i]=1;

  h[x][i]=1;

  jg[p][i]=1;

  if(t<k) search(t+1);

  if(t==k) { print(); return; }

  l[y][i]=0;

  h[x][i]=0;

  jg[p][i]=0;

  a[x][y]=0;

}

  }

}

int main()

{

 freopen("b.in","r",stdin);

 

   int i,j,x,y;

  memset(l,0,sizeof(l));

  memset(h,0,sizeof(h));

  memset(jg,0,sizeof(jg));

  

  for(i=1;i<=9;i++)

   for(j=1;j<=9;j++)

  {

    scanf("%d",&a[i][j]);

   if(a[i][j]!=0)

   { 

     l[j][a[i][j]]=1;

     h[i][a[i][j]]=1;

     jg[pd(i,j)][a[i][j]]=1;

   }

   if(a[i][j]==0)

    {

      k++;

      c[k][1]=i;

      c[k][2]=j;

    }

   }

   search(1);

 

   return 0;

}


by 30838 七月 29, 2016, 5:09 p.m.

Solution_ID:19474            DFS pascal

                   时间复杂度:Θ() 空间复杂度:Θ()

var
  a,b,c,v:array[1..9,1..9] of boolean;
  s:array[1..9,1..9] of 0..9;
  i,j:1..9;
procedure choose(e:byte);
var
  k,l,m:1..9;
begin
  if e=82 then
  begin
    for i:=1 to 9 do
    begin
      for j:=1 to 9 do
        write(s[i,j],' ');
      writeln;
    end;
    exit;
  end;
  k:=(e-1) div 9+1;
  l:=(e-1) mod 9+1;
  if v[k,l] then choose(e+1) else
  begin
    for m:=1 to 9 do
      if a[k,m] and b[l,m] and c[((k-1) div 3)*3+(l-1) div 3+1,m] then
      begin
        s[k,l]:=m;
        a[k,m]:=false;
        b[l,m]:=false;
        c[((k-1) div 3)*3+(l-1) div 3+1,m]:=false;
        choose(e+1);
        s[k,l]:=0;
        a[k,m]:=true;
        b[l,m]:=true;
        c[((k-1) div 3)*3+(l-1) div 3+1,m]:=true;
      end;
  end;
end;
Begin
  fillchar (a,sizeof(a),true);
  fillchar (b,sizeof(b),true);
  fillchar (c,sizeof(c),true);
  fillchar (v,sizeof(v),false);
  for i:=1 to 9 do
  begin
    for j:=1 to 9 do
    begin
      read(s[i,j]);
      if s[i,j]>0 then
      begin
        v[i,j]:=true;
        a[i,s[i,j]]:=false;
        b[j,s[i,j]]:=false;
        c[((i-1) div 3)*3+(j-1) div 3+1,s[i,j]]:=false;
      end;
    end;
    readln;

  end;

  choose(1);

end.


by 40305 七月 12, 2016, 4:24 p.m.

Solution_ID:18977            呵呵哒

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <stdlib.h>

#include <memory.h>

#include <cstdio>


int numbers[12][12];

int ro[12][12];

int co[12][12];

int ceo[12][12];


void printAns() {

    for (int i = 1;i <= 9;++i) {

        for (int j = 1;j <= 9;++j)

            printf("%d ",numbers[i][j]);

        printf("\n");

    }

}



//Each number before (r,c) and (r,c) has been searched

void dfs(int r,int c) {

    int i = c + 1;

    while (numbers[r][i] != 0) ++i;

    if (i > 9) {

        if (r == 9)

            printAns();

        else

            dfs(r + 1,0);

    }


    for (int num = 1;num <= 9;++num) {

        if (!ro[r][num] && !co[i][num] && !ceo[(r-1)/3*3+(i-1)/3+1][num]) {

            ro[r][num] = co[i][num] = ceo[(r-1)/3*3+(i-1)/3+1][num] = true;

            numbers[r][i] = num;

            dfs(r,i);

            ro[r][num] = co[i][num] = ceo[(r-1)/3*3+(i-1)/3+1][num] = false;

            numbers[r][i] = 0;

        }

    }


    return;

}


int main() {

    memset(numbers,0,sizeof(numbers));

    memset(ro,false,sizeof(co));

    memset(co,false,sizeof(co));

    memset(ceo,false,sizeof(co));

    for (int i = 1;i <= 9;++i)

        for (int j = 1;j <= 9;++j) {

            int num;

            scanf("%d",&num);

            numbers[i][j] = num;

            if (num != 0)

                ro[i][num] = co[j][num] = ceo[(i-1)/3*3+(j-1)/3+1][num] = true;

        }

    dfs(1,0);

}


by 41226 六月 22, 2016, 10:42 a.m.

Solution_ID:17981            这是真这不是梦~~~

                   时间复杂度:Θ(你猜) 空间复杂度:Θ(你猜)

#include<cstdio>
#include<cstring>
int map[11][11];
int ex,ey;
bool ife;

void print()
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
printf("%d ",map[i][j]);
printf("\n");
}
}
void dfs(int x,int y)
{
if(ife)return;
if(x==ex && y==ey)
{
ife=true;
print();
return;
}
while(map[x][y])
{
if(y<9)
{
y++;
}
else
{
x++;
y=1;
}
}
bool vis[11];
memset(vis,0,sizeof(vis));  //记录存在数字 
for(int i=1;i<=9;i++)vis[map[x][i]]=map[x][i]?1:0;
for(int i=1;i<=9;i++)vis[map[i][y]]=map[i][y]?1:0;
int xi,yi;
if(x<=3)xi=0;
else if(x<=6)xi=1;
else if(x<=9)xi=2;
if(y<=3)yi=0;
else if(y<=6)yi=1;
else if(y<=9)yi=2;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
vis[map[xi*3+i][yi*3+j]]=map[xi*3+i][yi*3+j]?1:0;
}
}
for(int i=1;i<=9;i++)
{
if(!vis[i])
{
map[x][y]=i;
dfs(x,y);
map[x][y]=0;
}
}
}


int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
scanf("%d",&map[i][j]);
bool ife=false;
for(int x=9;x>=1;x--)
{
for(int y=9;y>=1;y--)
{
if(!map[x][y] && !ife)
{
ife=true;
ex=x;
ey=y;
}
}
}
dfs(1,1);
return 0;
}


by 30310 四月 13, 2016, 10:13 p.m.

Solution_ID:17310            暴力c++

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

#include<cstdio>

using namespace std;

int sd[15][15];

bool vh[15][15],vl[15][15],vk[15][15];

void print()

{

int h,l;

printf("\n");

for(h=0;h<9;h++)

{

for(l=0;l<8;l++)printf("%d ",sd[h][l]);

printf("%d\n",sd[h][8]);

}

}

void ss(int h,int l)

{

if(h>=9)

{

print();

return;

}

if(l>=9)

{

ss(h+1,0);

return;

}

if(sd[h][l]!=0)

{

ss(h,l+1);

return;

}

int i;

for(i=1;i<=9;i++)

{

if(!vh[h][i]&&!vl[l][i]&&!vk[(h/3)*3+l/3][i])

{

vh[h][i]=1;

vl[l][i]=1;

vk[(h/3)*3+l/3][i]=1;

sd[h][l]=i;

ss(h,l+1);

vh[h][i]=0;

vl[l][i]=0;

vk[(h/3)*3+l/3][i]=0;

sd[h][l]=0;

}

}

}

int main()

{

int h,l;

bool bbb;

for(h=0;h<9;h++)

for(l=0;l<9;l++)

{

scanf("%d",&sd[h][l]);

vh[h][sd[h][l]]=true;

vl[l][sd[h][l]]=true;

vk[(h/3)*3+l/3][sd[h][l]]=true;

}

ss(0,0);

return 0;

}


by 34873 三月 18, 2016, 9:36 p.m.

Solution_ID:13621            纯暴力。。。233333333

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int lie[9][9],fang[9][9],hang[9][9],yuan[9][9];
bool lies[9][9],fangs[9][9],hangs[9][9];
void print(){
	for(int i=0;i<9;i++){
		
		for(int j=0;j<9;j++){
			cout<<yuan[i][j]+1<<" ";
		}cout<<endl;
	}
	
}
bool dfs(int i,int j){
	if(j==9){
		if(i==8){
		print();
		return 1;
	}
		else
		return dfs(i+1,0);
	}
	if(yuan[i][j]!=-1)
	{
		return dfs(i,j+1);
		
	}
	for(int a=0;a<9;a++){
		if(!lies[lie[i][j]][a]&&!hangs[hang[i][j]][a]&&!fangs[fang[i][j]][a]){
			lies[lie[i][j]][a]=1;
			hangs[hang[i][j]][a]=1;
			fangs[fang[i][j]][a]=1;
			yuan[i][j]=a;
			if(dfs(i,j+1))
			return 1;
			lies[lie[i][j]][a]=0;
			hangs[hang[i][j]][a]=0;
			fangs[fang[i][j]][a]=0;
			yuan[i][j]=-1;
		}
	}
	return 0;
}

int main(){
	memset(yuan,-1,sizeof(yuan));
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			hang[i][j]=i;
			lie[i][j]=j;
			fang[i][j]=(i/3)*3+j/3;
		}
	}
    for(int i=0;i<9;i++){
    	for(int j=0;j<9;j++){
    		int a;
    		cin>>a;
    		if(a!=0){
    			a--;
    			lies[lie[i][j]][a]=1;
			    hangs[hang[i][j]][a]=1;
			    fangs[fang[i][j]][a]=1;
			     yuan[i][j]=a;
			}
		}
	}
	dfs(0,0);
}

by 17480 十月 28, 2015, 8:20 a.m.

Solution_ID:7218            暴力是正义

                   时间复杂度:Θ(无(bu)法(hui)估计) 空间复杂度:Θ(o(1))

//其实直接深搜就可以了,也挺快的

//DLX什么东西 听起来很好吃

/*

作者:Dirak

题目:p2924 数独挑战

*/


#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
bool flag;
int sudoku[10][10];
void print()
{
for(int i=1; i<=9; i++)
{
for(int j=1; j<9; j++)
cout<<sudoku[i][j]<<" ";
cout<<sudoku[i][9]<<endl;
}
}
bool fit(int x, int y, int val)
{
for(int i=1; i<=9; i++)
{
if(val==sudoku[x][i]) return 0;
if(val==sudoku[i][y]) return 0;
}
for(int i=(x-1)/3*3+1; i<=(x-1)/3*3+3; i++)
       for(int j=(y-1)/3*3+1; j<=(y-1)/3*3+3; j++)
          if(val==sudoku[i][j]) return 0;
return 1;
}
void skip(int x, int y)
{
void DFS(int x, int y);
if(y==9)
DFS(x+1, 1);
else
DFS(x, y+1);
}
void DFS(int x, int y){
if(x==10 && y==1){
flag=1;
print();
return;
}
if(flag) return;
if(sudoku[x][y]) skip(x, y);
else
for(int i=1; i<=9; i++)
if(fit(x, y, i))
{
sudoku[x][y]=i;
skip(x, y);
sudoku[x][y]=0;
}
}
int main()
{
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
cin>>sudoku[i][j];
DFS(1, 1);


by 14893 二月 2, 2015, 1:48 p.m.

Solution_ID:6768            未知

                   时间复杂度:未知 空间复杂度:未知

var
a,b:array[1..9,1..9]of integer;
i,j,k,x,y:integer;
function h(i,j:integer):boolean;//用于判断下一个要填数的地方是否填了数(如果没填的话枚举的过程会退回上一步)
var
k,l:integer;
begin
for k:=j+1 to 9 do
if (b[i,k]=1)and(a[i,k]=0)then exit(true);
for k:=i+1 to 9 do
for l:=1 to 9 do
if (b[k,l]=1)and(a[k,l]=0)then exit(true);
exit(false);
end;
function f(i,j,k:integer):boolean;//用于判断在第i行第j列能否填k
var
l,m:integer;
begin
for l:=1 to i-1 do 
if a[l,j]=k then exit(false);
for l:=i+1 to 9 do
if a[l,j]=k then exit(false);
for l:=1 to j-1 do 
if a[i,l]=k then exit(false);
for l:=j+1 to 9 do
if a[i,l]=k then exit(false);
for l:=((i-1) div 3)*3+1 to ((i-1) div 3)*3+3 do
for m:=((j-1) div 3)*3+1 to ((j-1) div 3)*3+3 do
if a[l,m]=k then exit(false);
exit(true);
end;
procedure g(i,j:integer);//用于枚举
var
k:integer;
begin
if a[i,j]>0 then begin
if (i=9)and(j=9) then exit
else if (i<9)and(j=9) then g(i+1,1)
else g(i,j+1);
end
else
begin
for k:=1 to 9 do
if f(i,j,k) then 
begin 
a[i,j]:=k;  
if (i=9)and(j=9) then exit
else if (i<9)and(j=9) then g(i+1,1)
else g(i,j+1);
end;
if h(i,j) then a[i,j]:=0;
end;
end;
begin
for i:=1 to 9 do
begin 
for j:=1 to 9 do
begin
read(a[i,j]);
if a[i,j]=0 then inc(b[i,j]);//读入数据并用数组b标记要填的空以便函数h(i,j)运行
end;
readln;
end;
for i:=1 to 9 do
for j:=1 to 9 do
if a[i,j]=0 then//找到第一个要填的空
begin
g(i,j);//开始枚举
for x:=1 to 9 do
begin
for y:=1 to 9 do
write(a[x,y],' ');//输出
writeln;
end;
halt;
end;
end.


by 12587 八月 20, 2014, 1:22 p.m.

Solution_ID:5866            搜索

                   时间复杂度:未知 空间复杂度:未知

#include<iostream>
using namespace std;
int a[20][20];
int x[20][20];
int y[20][20];
int z[20][20];
int l[20][20],pd[20][20][20];
void dfs(int dx,int dy)
{
   if(dy==10) {dx++;dy=1;}
   if(a[dx][dy]!=0) dfs(dx,dy+1);
   if(dx==10&&dy==1)//想一想,为什么
   {
      for(int i=1;i<=9;i++)
      {
         for(int j=1;j<=9;j++)
         {
            cout<<a[i][j]<<" ";
         }
         cout<<endl;
      }
   }
   int j;
   int bb=((dx-1)/3)*3+(dy-1)/3+1;//取区域
   for(int i=1;i<=l[dx][dy];i++)//一个一个搜
   {
      j=pd[dx][dy][i];
      if(x[dx][j]==1||y[dy][j]==1||z[bb][j]==1) continue;
      x[dx][j]=1;//标记
      y[dy][j]=1;
      z[bb][j]=1;
      a[dx][dy]=j;
      dfs(dx,dy+1);
      x[dx][j]=0;//清除标记
      y[dy][j]=0;
      z[bb][j]=0;
      a[dx][dy]=0;        
   }
} 
int main()
{
   for(int i=1;i<=9;i++)//输入及预处理
   {
     for(int j=1;j<=9;j++)
     {
        cin>>a[i][j];
        x[i][a[i][j]]=1;
        y[j][a[i][j]]=1;
        z[((i-1)/3)*3+(j-1)/3+1][a[i][j]]=1;       
     }        
   }    
   for(int i=1;i<=9;i++)//这段程序自己想是为什么,是干什么的
   {
     for(int j=1;j<=9;j++)
     {
        if(a[i][j]!=0) continue;
        for(int k=1;k<=9;k++)
        {
           if(x[i][k]==1||y[j][k]==1||z[((i-1)/3)*3+(j-1)/3+1][k]==1)continue;
           pd[i][j][++l[i][j]]=k;
        }       
     }        
   }
   dfs(1,1); //递归
   return 0;    
} 
//如果你们有谁觉得这题很难,那么我无语了

by 7793 六月 12, 2014, 7:17 p.m.

Solution_ID:4505            未知

                   时间复杂度:未知 空间复杂度:未知

#include<stdio.h>
int area[10][10];
bool check[10][10],row[10][10],line[10][10];
void Dfs(int x,int y)
{
if(y==10&&x==9)
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)printf("%d ",area[i][j]);
printf("\n");
}
//ans++;
return;
}
else if(y==10&&x!=9)Dfs(x+1,1);
else if(area[x][y])Dfs(x,y+1);
else
{
for(int i=1;i<=9;i++)
{
if(!row[x][i]&&!line[y][i]&&!check[(x-1)/3*3+(y+2)/3][i])
{
row[x][i]=true;
line[y][i]=true;
check[(x-1)/3*3+(y+2)/3][i]=true;
area[x][y]=i;
Dfs(x,y+1);
row[x][i]=false;
line[y][i]=false;
check[(x-1)/3*3+(y+2)/3][i]=false;
area[x][y]=0;
}
}
}
}
int main()
{
 for(int i=1;i<=9;i++)
 for(int j=1;j<=9;j++)
 {
 scanf("%d",&area[i][j]);
 check[(i-1)/3*3+(j+2)/3][area[i][j]]=true;
 row[i][area[i][j]]=true;
 line[j][area[i][j]]=true;
 }
 Dfs(1,1);
 return 0;
}


by 9616 二月 15, 2014, 10:03 p.m.

Solution_ID:3612            DLX

                   时间复杂度:未知 空间复杂度:未知

DLX几类典型的应用之一。

注意输出每行末尾没有空格


by 5501 十一月 30, 2013, 7:43 p.m.