LeetCode Valid Sudoku数独有效性验证

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.

验证已经填好的数独是否合符规则。

思路：

行，列和小九宫分别检查就可以了。

有填好数字的就检查，没填写的可以不管。

但是也可以一起同时检查，时间效率稍微快一点，不过需要额外空间。

下面是分别检查行列和小九宫的程序：

class Solution {
public:
	static const int SQUARENUM = 9;
	static const int LITTLESQU = 3;

	bool isValidSudoku(vector
  
    > &board) 
	{
		vector
   
     vChar(SQUARENUM); for (int i = 0; i < SQUARENUM; i++) if (!rowValid(board[i])) return false; return colValid(board) && squValid(board); } bool rowValid(vector
    
      &vChar) { vector
     
       nine(SQUARENUM+1, 0); for (int i = 0; i < SQUARENUM; i++) { if (vChar[i] != '.') { int t = vChar[i] - '0'; if (nine[t]) return false; else nine[t] = 1; } } return true; } bool colValid(vector
      
        > &board) { vector
       
         nine(SQUARENUM+1,0); for (int i = 0; i < SQUARENUM; i++) { for (int j = 0; j < SQUARENUM; j++) { if (board[j][i]!= '.') { int t = board[j][i] - '0'; if (nine[t]) return false; else nine[t] = 1; } } nine.clear(); nine.resize(SQUARENUM+1, 0); } return true; } bool squValid(vector
        
          > &board) { vector
         
           nine(SQUARENUM+1, 0); for (int i = 0; i < SQUARENUM; i++) { for (int j = 0; j < SQUARENUM; j++) { int row = j/LITTLESQU + i/LITTLESQU*LITTLESQU, col = j%LITTLESQU + i%LITTLESQU*LITTLESQU; if (board[row][col]!= '.') { int t = board[row][col] - '0'; if (nine[t]) return false; else nine[t] = 1; } } nine.clear(); nine.resize(SQUARENUM+1, 0); } return true; } };
         
        
       
      
     
    
   
  

下面是leetcode上的，以空间的代价换取代码更加简洁，很好的思路：

http://discuss.leetcode.com/questions/215/valid-sudoku

class Solution {
public:
	bool isValidSudoku(vector
  
    > &board) 
	{
		vector
   
     > rows(9, vector
    
     (9, false)); vector
     
       > cols(9, vector
      
       (9, false)); vector
       
         > blocks(9, vector
        
         (9, false)); for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') continue; int c = board[i][j] - '1'; if (rows[i][c] || cols[j][c] || blocks[i - i % 3 + j / 3][c]) return false; rows[i][c] = cols[j][c] = blocks[i - i % 3 + j / 3][c] = true; } } return true; } };