#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <fstream>using namespace std;/*問題:Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudoku board could be partially filled, where empty cells are filled with the character '.'.A partially filled sudoku which is valid.Note:A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.分析:實質就是根據現有數獨中已經填充的數字，計算是否有解。數獨中每一行和每一列必須包含1~9的數字3*3的數組中必須包含1~9每個數字。此題關鍵是從何處開始遍歷，判斷是否能夠組成數組：采用每橫或每豎列是否每個數字只出現一次，對于每個棋盤判斷每個數字是否只出現一次；一旦不符合，重新嘗試填新的數字。實際上就是遞歸來做。關鍵是填充新的數字必須滿足已有條件：1：填充的數字已有出現次數不能超過總數題目中說判斷一個數獨棋盤是否有效，不需要一定有解，只需要判定該棋盤是否滿足其規則采用暴力破解：遍歷每一行，每一列分別看每個元素是否出現次數<=1次，輸入:9(數獨的長度，寬度與之相等)53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79輸出:yes關鍵:1 判斷子棋盤是否有效，可以遍歷一遍棋盤，每次計算出子棋盤的編號k=i /3 * 3 + j / 3例如(0,5)在第2個棋盤中，對應下標為1for(int i = 0 ; i < size ; i++){	for(int j = 0 ; j < size ; j++ )	{		if('.' == board.at(i).at(j))		{			continue;		}		//計算子棋盤編號		subBoard = i / 3 * 3 + j /3 ;		num = board[i][j] - '0' - 1;//多減1是因為下標從0開始		if(usedRow[i][num] || usedCol[j][num] || usedSubBoard[subBoard][num])		{			return false;		}		usedRow[i][num] = usedCol[j][num] = usedSubBoard[subBoard][num] = 1;	}}*/class Solution{public:	bool isValidSudoku(vector<vector<char> > &board)	{		if(board.empty())		{			return false;		}		int size = board.size();		int usedRow[9][9] = {0};		int usedCol[9][9] = {0};		int usedSubBoard[9][9] = {0};		int subBoard;		int num;		for(int i = 0 ; i < size ; i++)		{			for(int j = 0 ; j < size ; j++ )			{				if('.' == board.at(i).at(j))				{					continue;				}				//計算子棋盤編號				subBoard = i / 3 * 3 + j /3 ;				num = board[i][j] - '0' - 1;//多減1是因為下標從0開始				if(usedRow[i][num] || usedCol[j][num] || usedSubBoard[subBoard][num])				{					return false;				}				usedRow[i][num] = usedCol[j][num] = usedSubBoard[subBoard][num] = 1;			}		}		return true;	}};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 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);	}	bool result = solution.isValidSudoku(board);	if(result)	{		cout << "yes" << endl;	}	else	{		cout << "no" << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}