poj2676 Sudoku(數獨,dfs+剪枝）

思路來源

https://blog.csdn.net/xiaozhuaixifu/article/details/12253507

題意

給定一個不完整9*9數獨，

未填部分用0表示，

恢復數獨，並打印

題解

在讀入的時候，

我們開幾個數組，

sudoku[9][9]，相當於這張數獨地圖，上面記錄值

checkrow[9][10]，第i行，是否出現過數v，1<=v<=9

checkcol[9][10]，第j列，是否出現過數v，1<=v<=9

square[9][10]，第k塊，是否出現過數v，1<=v<=9

塊的定義，

即圖片中漢字數字順序，對應0-8塊，

k=i/3*3+j/3可表示。

//圖片來源於網絡http://blog.sina.com.cn/s/blog_4e92a29f010171dc.html

我們從（0,0）開始dfs，

如果行末，就dfs下一行行首；

如果非行末，就dfs本行下一列，

如果到（9,0）了，說明前面均無衝突。

然後就是dfs經典三段論。

①試數，對應修改

②向更深層次搜索

③（如果能到這裏，說明②失敗）將①還原

心得

博主這篇文章真的是好評，

代碼風格也很好，剪枝也減的恰到好處，

搜到一個可行解，isdone就返回，

雖然沒加一句註釋，但通俗易懂。

QAQ數獨的確是一種經典題，還是要多練爲妙

全oj大概有那麼五六個數獨題吧，

16*16的，靶型數獨的，以後再補吧

代碼

講道理，貼代碼裏面的i，個人覺得，好吃藕

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <string.h>
#include <cstdio>
#include <cmath>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const double INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
char tmp[9];
int sudoku[9][9];
bool square[9][10];//第i個3*3塊,數j是否已經出現 
bool checkrow[9][10];//第i行,數j是否已經出現 
bool checkcol[9][10];//第i列,數j是否已經出現 
bool isdone;//是否搜到一個可行解 
void init()
{
	mem(checkrow,0);
	mem(checkcol,0);
	mem(square,0);
	isdone=0; 
}
void dfs(int i,int j)//當前判sodaku[i][j]是否合法 
{
	if(i==9)
	{
		isdone=1;//搜到一個答案
		rep(i,0,8)
		{
			rep(j,0,8)
			{
			    printf("%d",sudoku[i][j]);
			}
			puts("");
		}
		return;
	}
	if(isdone)return;//已經搜到一個可行解了,把剩下的剪枝
	if(sudoku[i][j])//這裏已經置入一個數了 
	{
		if(j==8)dfs(i+1,0);//搜到行末了，新開一行
		else dfs(i,j+1); 
	}
	else
	{
		rep(v,1,9)
		{
			int k=i/3*3+j/3;//第k塊 
			if(!checkrow[i][v]&&!checkcol[j][v]&&!square[k][v])//o(1)查重的操作
			{
				//先試試，v能不能行 
				sudoku[i][j]=v;
				checkrow[i][v]=1;
				checkcol[j][v]=1;
				square[k][v]=1;
				//向後續搜索 
				if(j==8)dfs(i+1,0);
				else dfs(i,j+1);
				//能運行到這句，說明不行，改回來 
				sudoku[i][j]=0;
				checkrow[i][v]=0;
				checkcol[j][v]=0;
				square[k][v]=0;
			} 
		}
	} 
} 
int main()
{
	int t;
	sci(t);
	while(t--)
	{
		init();
		rep(i,0,8)
		{
			scanf("%s",tmp);
			rep(j,0,8)
			{
				int v=tmp[j]-'0';
				sudoku[i][j]=v;
				if(v)
				{
					int k=i/3*3+j/3;//第k塊
					checkrow[i][v]=1;//i行出現過v 
					checkcol[j][v]=1;//j列出現過v 
					square[k][v]=1;//k塊出現過v 
				}
			}
		}
		dfs(0,0);
	}
    return 0;
}