36. Valid Sudoku

问题描述

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.

验证数独游戏中的九宫格是否有效。

思路

先验证横的九条，再验证竖着的九条；最后将大九宫格看成9个小宫格，循环验证这9个九宫格是否有效。

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char> >& board) {
		int m = board.size();
		int n = board[0].size();
		for(int i=0;i<9;i++) {
			bool exists1[10]={
				0
			};
			bool exists2[10]={
				0
			};
			for(int j=0;j<9;j++) {
				// 横的 
				char v1 = board[i][j];
				if(v1!='.'&&exists1[v1-'0']) {
					return false;
				} else if(v1!='.') {
					exists1[v1-'0']=true;					
				}
				// 纵的
				char v2 = board[j][i];
				if(v2!='.'&&exists2[v2-'0']) {
					return false;
				} else if(v2!='.') {
					exists2[v2-'0']=true;
				}
			}
		}		
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++){
				// 遍历九宫格
				int x=i*3;
				int y=j*3;
			 	bool exists[10]={
	 				0
	 			};
			 	for(int p=0;p<3;p++) {
	 				for(int q=0;q<3;q++) {
				 		char v = board[x+p][y+q];
				 		if(v!='.'&&exists[v-'0']) {
				 			return false;
		 				} else if(v!='.') {
				 			exists[v-'0']=true;
				 		}
				 	}
	 			}
			}
		}
		return true;
    }
};

因为可能构造测试用例有些麻烦，就把我的测试代码也贴一下

int main() {
	vector<vector<char> > board(9);
	string strs[9] = {".87654321","2........","3........","4........","5........","6........","7........","8........","9........"};
	for(int i=0;i<9;i++) {
		vector<char> vec(9);
		for(int j=0;j<9;j++) {
			char ch = strs[i][j];
			vec[j]=ch;
		}
		board[i]=vec;
	}
	Solution s;
	cout<<s.isValidSudoku(board)<<endl;
}