关于一种逻辑推理的方法
  • 板块P1784 数独
  • 楼主caojiaming
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/11/28 11:37
  • 上次更新2023/10/27 01:07:18
查看原帖
关于一种逻辑推理的方法
775551
caojiaming楼主2022/11/28 11:37

我写了一种逻辑推理的代码 没想到全RE

//主要思想就是看每个未填的方块有哪些数不能填,就排除掉,如果只有一个数可以填,就填上这个数
#include <bits/stdc++.h>
using namespace std;
int a[10][10];//存数独
int m[10][10][10];//存可能的数
void myset()//不加my会重定义
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			for(int k=0;k<=9;k++)
			{
				m[i][j][k]=k;
			}
		}
	}
}
void input()//读入
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			cin>>a[i][j];
		}
	}
}
void print()//输出
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<"\n";
	}
}
int determined(int x,int y)//看确不确定
{
	int cnt=0;
	int o=0;
	for(int i=1;i<=9;i++)
	{
		cnt+=(m[x][y][i]!=0);
		if(m[x][y][i]!=0)
		{
			o=i;
		}
	}
	if(cnt==0)
	{
		return 0;
	}
	else if(cnt==1)
	{
		return o;
	}
	return 0;
}
bool no_answer()//判断有没有答案
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			int k;
			for(k=1;k<=9;k++)
			{
				if(m[i][j][k]!=0)
				{
					break;
				}
			}
			if(k==10)
			{
				return 1;
			}
		}
	}
	return 0;
}
bool not_full()//判断有没有填满
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			if(a[i][j]==0)
			{
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	myset();
	input();
	while(not_full())//这样推理下去直到所有方块填满
	{
		for(int i=1;i<=9;i++)//遍历
		{
			for(int j=0;j<=9;j++)
			{
				if(a[i][j])
				{
					continue;
				}
				//先看行列再看区块
				for(int k=1;k<=9;k++)
				{
					if(a[i][k])
					{
						m[i][j][a[j][k]]=0;
					}
				}
				for(int k=1;k<=9;k++)
				{
					if(a[k][j])
					{
						m[i][j][a[k][j]]=0;
					}
				}
				int x1,y1,x2,y2;//标记起点和终点
				for(int pd1=1,pd2=3;pd2<=9;pd1+=3,pd2+=3)//寻找要看的方块的起点和终点
				{
					if(pd1<=i&&pd2>=i)
					{
						x1=pd1;
						y1=pd2;
						for(int pd3=1,pd4=3;pd4<=9;pd3+=3,pd4+=3)
						{
							if(pd3<=j&&pd4>=j)
							{
								x2=pd3;
								y2=pd4;
								break;
							}
						}
						break;
					}
				}
				for(int k=x1;k<=y1;k++)
				{
					for(int L=x2;L<=y2;L++)
					{
						if(a[k][L])
						{
							m[i][j][a[k][L]]=0;
						}
					}
				}
			}
		}
		if(no_answer())
		{
			cout<<"no answer!";
			return 0;
		}
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				int d=determined(i,j);
				if(d)
				{
					a[i][j]=d;
				}
			}
		}
	}
	print();
	return 0;
}

2022/11/28 11:37
加载中...