数独题深搜求助
  • 板块P1784 数独
  • 楼主Heerer
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/8/31 22:37
  • 上次更新2023/11/4 08:13:19
查看原帖
数独题深搜求助
559834
Heerer楼主2021/8/31 22:37

最近一时兴起想写个程序帮我检查数独题,正好洛谷有这道题。但怎奈何鄙人初学c++数月,搜索不是很会写。。网上也没有“平易近人”的教程,题解写的与我写的更是不尽相同。所以我想请教各位大佬看看我写的还能不能补救一下。 源代码如下

#include<iostream>
using namespace std;
int a[10][10],x1,y1,i,j;
void dfs(int x,int y)
{
	if(x==10)
	{
		if(y==9)
			return;
		else
		{
			x=1;
			y++;
		}
	}
	if(a[x][y]==0)
	{
		int m[10]={0},n[10]={0},t[10]={0};
		x1=(x+2)/3;
		y1=(y+2)/3;
		for(i=1;i<=9;i++)
		{
			m[a[i][y]]=1;
			n[a[x][i]]=1;
		}
		for(i=3*y1-2;i<=3*y1;i++)
			for(j=3*x1-2;j<=3*x1;j++)
				t[a[j][i]]=1;
		for(i=1;i<=9;i++)
		{		 
				if(m[i]==0&&n[i]==0&&t[i]==0)
				{
					a[x][y]=i;
					dfs(x+1,y);
				}	
		} 
	}
	else
		dfs(x+1,y); 
}
int main()
{
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++)
				cin>>a[j][i];
	dfs(1,1);
	for(i=1;i<=9;i++)
	{
		for(j=1;j<=9;j++)
		{
			cout<<a[j][i]<<" ";
		}
		cout<<endl;
	}	
} 

PS.目前程序的问题是:当一个位置没有可放置的数字时(即无论填什么都会重复时),程序不会退回到上一步继续尝试,而是退出了dfs直接输出了。

2021/8/31 22:37
加载中...