每天算法之三十：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.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

判断一个给定的二重向量是不是九宫格，要求有三个：每一行，每一列，每一个3*3的单元都是数字1-9的排列，出现且只能出现一次。当然，‘.’可以代替任意一个数字都是合法的。

我们要做的也很简单，依次判断一行是不是仅这一次，这一列是不是仅这一次，每一个小单元是不是仅这一次。我们借助一个九个元素的向量来表示数字出现的次数。比较难以理解的就是最后的小单元统计的时候，起始位置是怎样计算的。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        int row,col,block;
        char ch;
        vector<int> marks(9,0);
        //Rows
        for (row = 0; row < 9; ++row) {
            marks.assign(9, 0);
            
            for (col = 0; col < 9; ++col) {
                ch = board[row][col];
                
                if (ch != '.') {
                    if (marks[ch - '1'] > 0) {
                        return false;
                    }
                    else {
                        ++marks[ch - '1'];
                    }
                }
            }
        }
        //Cols
         for (col = 0; col < 9; ++col) {
            marks.assign(9, 0);
            
            for (row = 0; row < 9; ++row) {
                ch = board[row][col];
                
                if (ch != '.') {
                    if (marks[ch - '1'] > 0) {
                        return false;
                    }
                    else {
                        ++marks[ch - '1'];
                    }
                }
            }
        }
        //Blocks
        for(block = 0;block<9;block++)
        {
          int start_row = (block/3)*3,start_col = (block%3)*3;
          marks.assign(9,0);
          for(row = start_row;row<(start_row+3);row++)
          {
            for(col = start_col;col<(start_col+3);col++)
            {
              ch = board[row][col];
              if('.'!=ch)
              {
                if(marks[ch-'1']>0)
                  return 0;
                else
                  marks[ch-'1']++;
              }
            }
          }
        }
        return true;
    }
};