#include <iostream>#include <stdio.h>#include <vector>#include <fstream>using namespace std;/*問(wèn)題: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.分析:這是搜索是否有解的問(wèn)題，廣度優(yōu)先搜索最優(yōu)解，深度優(yōu)先搜索確定是否有解。因此本題應(yīng)該用深度優(yōu)先搜索?？搭}目，如果擺放新的元素不成功，應(yīng)該是要回溯的。因此，此題應(yīng)該是回溯來(lái)做。每一次嘗試擺放一個(gè)1~9中的某個(gè)元素，如果擺放不成功，就用另一個(gè)元素替換，如果最終棋盤擺滿了，就輸出結(jié)果。如何判定沒(méi)有結(jié)果，如果1判斷是否滿足可行解，只需要當(dāng)前board[i][j]元素為c是否在行號(hào)，列號(hào)，子棋盤擺放過(guò)	判斷子棋盤上的9個(gè)元素是否與給定元素重復(fù)，先確定 子棋盤的行號(hào)=行號(hào)	給定位置(row,jcol)計(jì)算對(duì)應(yīng)子棋盤的行號(hào)(x,y)	x = 3 * (row / 3)	y = 3 * (col / 3)	子棋盤編號(hào) = 3 *(row / 3) + col /3 = 3 + 2 = 5,行號(hào)確定大的子棋盤編號(hào)，列號(hào)確定小的子棋盤編號(hào)	子棋盤元素下標(biāo) = 3 * (col / 3) + col % 3 = 3 * 2 + 8 % 3 = 8,其實(shí)就是將列分成3等份，然后取余數(shù)	比如給定元素(5,8)，對(duì)應(yīng)第6子棋盤中（編號(hào)為5)中第8個(gè)元素	這里由于采用i為0~8，i默認(rèn)為列號(hào)	則新的子棋盤編號(hào)=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個(gè)元素是否與給定元素重復(fù)，先確定 子棋盤的行號(hào)=行號(hào)			給定位置(row,jcol)計(jì)算對(duì)應(yīng)子棋盤的行號(hào)(x,y)			x = 3 * (row / 3)			y = 3 * (col / 3)			子棋盤編號(hào) = 3 *(row / 3) + col /3 = 3 + 2 = 5,行號(hào)確定大的子棋盤編號(hào)，列號(hào)確定小的子棋盤編號(hào)			子棋盤元素下標(biāo) = 3 * (col / 3) + col % 3 = 3 * 2 + 8 % 3 = 8,其實(shí)就是將列分成3等份，然后取余數(shù)			比如給定元素(5,8)，對(duì)應(yīng)第6子棋盤中（編號(hào)為5)中第8個(gè)元素			這里由于采用i為0~9，i默認(rèn)為列號(hào)			則新的子棋盤編號(hào)=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ū)域處擺放下一個(gè)元素，這里直接用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) = '.';							}						}					}					//如果一直沒(méi)有得到結(jié)果，說(shuō)明無(wú)效					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;}