C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 416K, 提交时间: 2022-10-10 20:23:10

#include<iostream>
using namespace std;
bool sign=false;
int num[9][9];
void Input();
void Output();
bool Check(int n,int key);
int D(int n);
int main()
{
	Input();
	D(0);
	Output();
}
void Input()
{
	char temp[9][9];
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			cin>>temp[i][j];
			num[i][j]=temp[i][j]-'0';
		}
	}
}

void Output()
{
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			cout<<num[i][j]<<" ";
		}
		cout<<endl;
		}
	}

bool Check(int n,int key)
{
	int i;
	for(i=0;i<9;i++)
	{
		int j=n/9;
		if(num[j][i]==key)return false;
	}
for(i=0;i<9;i++)
{
	int j=n%9;
	if(num[i][j]==key)return false;
	
}
int x=n/9/3*3;
int y=n%9/3*3;
for(i=x;i<x+3;i++)
{
	for(int j=y;j<y+3;j++)
	{
		if(num[i][j]==key)return false;
	}
}
return true;
}

int D(int n)
{
	if(n>80)
	{
		sign=true;
		return 0;
	}
	if(num[n/9][n%9]!=0)
	{
		D(n+1);
	}
	else{
	
		for(int i=1;i<=9;i++)
		{
			if(Check(n,i)==true)
			{
				num[n/9][n%9]=i;
				D(n+1);
				if(sign==true)return 0;
				num[n/9][n%9]=0;
			}
		}	
	}
    return n;
} 

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 376K, 提交时间: 2020-09-16 15:59:19

#include<bits/stdc++.h>
using namespace std;
int a[1001];
bool f=0;
bool check(int x,int num)
{
	int i,y=x%9;
	x/=9;
	for(i=0; i<9; i++)
	{
		if(a[i*9+y]==num&&i!=x)
		{
			return 0;
		}
		if(a[x*9+i]==num&&i!=y)
			return 0;
	}
	int b=x/3*3,c=y/3*3;
	for(i=b;i<b+3;i++)
	{
		for(int j=c;j<c+3;j++)
		{
			if(a[i*9+j]==num&&i!=x&&j!=y)
			return 0;
		}
	}
	return 1;
}
void dfs(int x)
{
	if(x>80)
	{
		f=1;
		return ;
	}
	if(a[x])
	{
		dfs(x+1);
		return ;
	}
	for(int i=1;i<10;i++)
	{
		if(check(x,i))
		{
			a[x]=i;
			dfs(x+1);
			if(f)
			return ;
			a[x]=0;
		}
	}
}
int main()
{
	int i,j;
	for(i=0; i<9; i++)
		for(j=0; j<9; j++)
			cin>>a[i*9+j];
	dfs(0);
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			if(j)
			cout<<" ";
			cout<<a[i*9+j];
		}
		cout<<endl;
	}
	return 0;
}