C++(g++ 7.5.0) 解法, 执行用时: 254ms, 内存消耗: 452K, 提交时间: 2023-07-24 17:00:41

#include<bits/stdc++.h>
using namespace std;
int a[10][10];
int check(int x,int y,int u)
{
	for(int i=0; i<9; ++i)
	{
		if(a[i][y]==u||a[x][i]==u) return 0;
	}
	int xx=x/3*3,yy=y/3*3;
	for(int i=xx; i<=xx+2; ++i)
		for(int j=yy; j<=yy+2; ++j)
			if(a[i][j]==u) return 0;
	return 1;
}
void dfs(int x,int y)
{
	if(x==9&&y==0)
	{
		for(int i=0; i<9; ++i)
		{
			for(int j=0; j<9; ++j)
				cout<<a[i][j]<<" ";
			cout<<'\n';
        }
		return ;
	}
	if(y==9) dfs(x+1,0);
	else
	{
		if(a[x][y]) dfs(x,y+1);
		else
			for(int i=1; i<=9; ++i)
			{
				if(check(x,y,i))
				{
					a[x][y]=i;
					dfs(x,y+1);
					a[x][y]=0;
				}
			}
	}
}
int main()
{
	for(int i=0; i<9; ++i)
		for(int j=0; j<9; ++j) cin>>a[i][j];
	dfs(0,0);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 74ms, 内存消耗: 492K, 提交时间: 2019-04-13 13:30:26

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10][10];
bool dfs(int x,int y){
	if(x>9){
		for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)printf("%d%c",a[i][j]," \n"[j==9]);
	}
	if(a[x][y]){
		if(y==9)return dfs(x+1,1);
		else return dfs(x,y+1);
	}
	bool f=0;
	int mark[10]={0};
	for(int k=1;k<=9;k++)mark[a[x][k]]=mark[a[k][y]]=1;
	for(int k=(x-1)/3*3+1;k<=(x-1)/3*3+3;k++)
	for(int l=(y-1)/3*3+1;l<=(y-1)/3*3+3;l++)mark[a[k][l]]=1;
	for(int i=1;!f&&i<=9;i++)
	if(!mark[i]){
		a[x][y]=i;
		//printf("%d\n",a[1][1]);
		if(y==9)f=dfs(x+1,1);
		else f=dfs(x,y+1);
		a[x][y]=0;
	}
	return f;
}
int main(){
	for(int i=1;i<=9;i++)
	for(int j=1;j<=9;j++)scanf("%d",&a[i][j]);
	dfs(1,1);
	
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 47ms, 内存消耗: 484K, 提交时间: 2020-02-17 19:29:26

#include<iostream>
using namespace std;
int a[9][9];
bool check(int,int,int);
bool dfs(int);
int main()
{
	int i,j;
	for(i=0;i<9;i++)
	for(j=0;j<9;j++)
	cin>>a[i][j];
	dfs(0);
	for(i=0;i<9;i++)
	{
		for(j=0;j<8;j++)
		cout<<a[i][j]<<" ";
		cout<<a[i][8]<<'\n';
	}
	return 0;
}
bool dfs(int x)
{
	if(x==81) return true;
	int r=x/9,c=x%9,i;
	if(a[r][c]) return dfs(x+1);
	else
	for(i=1;i<=9;i++)
	if(check(r,c,i))
	{
		a[r][c]=i;
		if(dfs(x+1)) return true;
		else a[r][c]=0;
	}
	return false;
}
bool check(int r,int c,int x)
{
	int i,j,k=r+3-r%3,l=c+3-c%3;
	for(i=0;i<9;i++)
	if(a[r][i]==x||a[i][c]==x) return false;
	for(i=k-3;i<k;i++)
	for(j=l-3;j<l;j++)
	if(a[i][j]==x) return false;
	return true;
}