数独只有唯一解吗?
  • 板块P1784 数独
  • 楼主JerryMain
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/10/25 22:48
  • 上次更新2023/10/27 05:52:01
查看原帖
数独只有唯一解吗?
582900
JerryMain楼主2022/10/25 22:48

蒟蒻求助

#include "cmath"
using namespace std;
int a[10][10];
void print()
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
	exit(0);
}
bool line(int k,int x)
{
	for(int i=1;i<=9;i++)
		if(a[x][i]==k)
			return false;
	return true;
}
bool con(int k,int y)
{
	for(int i=1;i<=9;i++)
		if(a[i][y]==k)
			return false;
	return true;
}
bool block(int k,int x,int y)
{
	x=floor((double)x/3.1)*3+1;
	y=floor((double)y/3.1)*3+1;
	for(int i=x;i<=x+2;i++)
		for(int j=y;j<=y+2;j++)
		if(a[i][j]==k)
			return false;
	return true;
}
void dfs(int x,int y)
{
	if(a[x][y]!=0)
		dfs(x+1,y);
	if(x>9)
		dfs(1,y+1);
	if(y==9&&x>9)
	{
		print();
		return;
	}
	for(int i=1;i<=9;i++)
		if(line(i,x)&&con(i,y)&&block(i,x,y))
		{
			a[x][y]=i;
			dfs(x+1,y);
		}
	a[x][y]=0;
}
int main()
{
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
			cin>>a[i][j];
	dfs(1,1);
}
/*
我的样例解:

8 6 5  2 1 4  3 7 9
1 2 9  6 3 7  5 8 4
4 7 3  8 5 9  6 2 1

2 5 4  3 7 1  8 9 6
3 1 6  9 2 8  7 4 5
9 8 7  4 6 5  1 3 2

5 3 1  7 4 2  9 6 8
6 4 8  5 9 3  2 1 7
7 9 2  1 8 6  4 5 3
*/

这个解应该是对的,但数独只有唯一解吗?

2022/10/25 22:48
加载中...