#include <iostream>#include <stdio.h>#include <vector>#include <fstream>using namespace std;/*問題:Write a PRogram to solve a Sudoku puzzle by filling the empty cells.Empty cells are indicated by the character '.'.You may assume that there will be only one unique solution.A sudoku puzzle......and its solution numbers marked in red.分析:這是搜索是否有解的問題，廣度優(yōu)先搜索最優(yōu)解，深度優(yōu)先搜索確定是否有解。因此本題應(yīng)該用深度優(yōu)先搜索。看題目，如果擺放新的元素不成功，應(yīng)該是要回溯的。因此，此題應(yīng)該是回溯來做。每一次嘗試擺放一個1~9中的某個元素，如果擺放不成功，就用另一個元素替換，如果最終棋盤擺滿了，就輸出結(jié)果。如何判定沒有結(jié)果，如果1判斷是否滿足可行解，只需要當(dāng)前board[i][j]元素為c是否在行號，列號，子棋盤擺放過	判斷子棋盤上的9個元素是否與給定元素重復(fù)，先確定 子棋盤的行號=行號	給定位置(row,jcol)計算對應(yīng)子棋盤的行號(x,y)	x = 3 * (row / 3)	y = 3 * (col / 3)	子棋盤編號 = 3 *(row / 3) + col /3 = 3 + 2 = 5,行號確定大的子棋盤編號，列號確定小的子棋盤編號	子棋盤元素下標(biāo) = 3 * (col / 3) + col % 3 = 3 * 2 + 8 % 3 = 8,其實就是將列分成3等份，然后取余數(shù)	比如給定元素(5,8)，對應(yīng)第6子棋盤中（編號為5)中第8個元素	這里由于采用i為0~8，i默認(rèn)為列號	則新的子棋盤編號=board[ 3 * (row / 3) + i / 3 ][3 * (col / 3) + i % 3]	subBoardIndex = 3 * (row / 3) + i / 3;	index = 3 * (col / 3) + i % 3;*/class Solution {public:	bool isValidSudoku(vector<vector<char> > &board , int row  , int col , char c)	{		if(board.empty())		{			return false;		}		int size = board.size();		int subBoardIndex;		int index;		for(int i = 0 ; i < 9 ; i++)		{			if(board[i][col] != '.' && board[i][col] == c)			{				return false;			}			if(board[row][i] != '.' && board[row][i] == c)			{				return false;			}			/*			判斷子棋盤上的9個元素是否與給定元素重復(fù)，先確定 子棋盤的行號=行號			給定位置(row,jcol)計算對應(yīng)子棋盤的行號(x,y)			x = 3 * (row / 3)			y = 3 * (col / 3)			子棋盤編號 = 3 *(row / 3) + col /3 = 3 + 2 = 5,行號確定大的子棋盤編號，列號確定小的子棋盤編號			子棋盤元素下標(biāo) = 3 * (col / 3) + col % 3 = 3 * 2 + 8 % 3 = 8,其實就是將列分成3等份，然后取余數(shù)			比如給定元素(5,8)，對應(yīng)第6子棋盤中（編號為5)中第8個元素			這里由于采用i為0~9，i默認(rèn)為列號			則新的子棋盤編號=board[ 3 * (row / 3) + i / 3 ][3 * (col / 3) + i % 3]			*/			subBoardIndex = 3 * (row / 3) + i / 3;			index = 3 * (col / 3) + i % 3;			if(board[subBoardIndex][index] != '.' && board[subBoardIndex][index] == c)			{				return false;			}		}		return true;	}	bool isSolved(vector<vector<char>>& board)	{		if(board.empty())		{			return false;		}		int size = board.size();		for(int i = 0 ; i < size ; i++)		{			for(int j = 0 ; j < size ; j++ )			{				if('.' == board.at(i).at(j))				{					//嘗試在空白的區(qū)域處擺放下一個元素，這里直接用cha					for(char c = '1' ; c <= '9' ; c++)					{						//如果擺放有效，繼續(xù)處理						if(isValidSudoku(board , i , j , c))						{							board.at(i).at(j) = c;							//牛逼，直接用遞歸判斷下一次是否擺放成功							if(isSolved(board))							{								return true;							}							else							{								board.at(i).at(j) = '.';							}						}					}					//如果一直沒有得到結(jié)果，說明無效					return false;				}			}		}		return true;	}    void solveSudoku(vector<vector<char>>& board) {		if(board.empty())		{			return;		}		bool isSolve = isSolved(board);		_isSolved = isSolve;	}public:	bool _isSolved;};vector<string> readFile(string& fileName){	vector<string> results;	if(fileName.empty())	{		return results;	}	ifstream file(fileName , ios::in);	if(!file)	{		cout << "can't open file" << endl;		return results;	}	const int maxSize = 1024;	char str[maxSize];	while(!file.eof())	{		file.getline(str , maxSize);		string s(str);		results.push_back(s);	}	file.close();	return results;}void print(vector< vector<char> >& board){	if(board.empty())	{		cout << "no result" << endl;	}	int size = board.size();	for(int i = 0 ; i < size ; i++)	{		for(int j = 0 ; j < size ; j++ )		{			cout << board.at(i).at(j);		}		cout << endl;	}}void process(){	vector< vector<char> > board;	string s;	int size;	Solution solution;	board.clear();	vector<string> strs = readFile(string("data.txt"));	int len = strs.size();	for(int i = 0 ; i < len ; i++)	{		s = strs.at(i);		vector<char> str;		size = s.length();		for(int i = 0 ; i < size ; i++)		{			str.push_back(s.at(i));		}		board.push_back(str);	}	solution.solveSudoku(board);	if(solution._isSolved)	{		print(board);	}	else	{		cout << "no" << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}