POJ 2676 Sudoku (數獨)

經典搜索問題，主要是時間上的優化，我用了三個輔助數組記錄信息 row[i][k] = 1表示第i行數字k已經被使用，col[j][k] = 1表第j列數字k已經被使用，blo[i][k]表示第i個小九宮格中數字k已經被使用

還有很重要的一個優化（沒有優化的話可能會超時，或者非常慢，像POJ討論區裡有很多說正著搜超時，倒著搜0ms，這的確是一個可以用的方法，但是有一定的隨機性），每次填數字時，先掃描一遍整個矩陣，找出可選數字情況最少的那個0所在的地方，優先填這裡，這樣會使得搜索樹盡可能的“瘦“一些，效果會非常明顯

代碼

/*
poj    2676
236K	0MS
*/ 

#include
#include

#define MAXN 10
#define MAX_INT 2147483647

using namespace std;

bool flag = false;
int matrix[MAXN][MAXN], row[MAXN][MAXN], col[MAXN][MAXN], blo[MAXN][MAXN];
//用int判斷比bool判斷要快！ 
int area[MAXN][MAXN] = {
						{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
						{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
						{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
						{0, 7, 7 ,7, 8, 8, 8, 9, 9, 9}
						};

void solve(int cnt)
{
	if(flag)
		return ;
	if( !cnt )
	{
		flag = true;
		for(int i = 1;i <= 9;i ++)
		{
			for(int j = 1;j <= 9;j ++)
				cout<>cases;
	while(cases --)
	{
		memset(row, 0, sizeof(row));
		memset(col, 0, sizeof(col));
		memset(blo, 0, sizeof(blo));
		memset(matrix, 0, sizeof(matrix));
		flag = false;
		cnt = 0;
		for(int i = 1;i <= 9;i ++)
		{
			for(int j = 1;j <= 9;j ++)
			{
				char ch;
				cin>>ch;
				matrix[i][j] = ch - '0';
				row[i][matrix[i][j]] = 1;
				col[j][matrix[i][j]] = 1;
				blo[area[i][j]][matrix[i][j]] = 1;
				if( !matrix[i][j] )
					cnt ++;
			}
		}
		solve(cnt);
	}
	return 0;
}