蓝桥杯备考：DFS之数独

这道题的意思是每个3*3的格子只能有1到9九个数字，每行只能有1到9九个数字，每列也只能有1到9每个数字，我们可以开个col[N][N]表示某一列出现过的数字

row[N][N]表示某一行出现的数字,st[N][N][N]表示每个3*3的子矩阵里出现的数字

话说到这里，我们已经可以实现代码了

#include <iostream>
using namespace std;

const int N = 15;
int a[N][N];
bool col[N][N];
bool row[N][N];
bool st[N][N][N];
bool dfs(int i,int j)
{
	if(j==9)
	{
		j=0;
		i++;
	}
	if(i==9)
	{
		return true;
	}
	if(a[i][j])
	{
		return dfs(i,j+1);
	}
	for(int x = 1;x<=9;x++)
	{
		if(col[j][x] || st[i/3][j/3][x]||row[i][x]) continue;
		col[j][x] = st[i/3][j/3][x] = row[i][x] = true;
		a[i][j] = x;
		if(dfs(i,j+1)) return true;
		col[j][x] = st[i/3][j/3][x] = row[i][x]= false;
		a[i][j] = 0; 
	}
	return false;
}
int main()
{
	for(int i = 0;i<9;i++)
	{
		for(int j = 0;j<9;j++)
		{
			cin >> a[i][j];
			int x = a[i][j];
			if(x){
			col[j][x] = true;
			st[i/3][j/3][x] = true;
			row[i][x] = true;
	     	}
		}
	}
	dfs(0,0);
	for(int i = 0;i<9;i++)
	{
		for(int j = 0;j<9;j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	
	
	return 0;
}