leetcode-36. Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits  1-9  without repetition. Each column must contain the digits  1-9  without repetition. Each of the 9  3x3  sub-boxes of the grid must contain the digits  1-9  without repetition. A partially filled sudoku which is valid. The Sudoku board could be partially filled, where empty cells are filled with the character  '.' . Example 1: Input: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] Output: true Example 2: Input: [   ["8","3",".",".","7",".",".",".","."],   ["6",".",".","1","9","5",".",".","."],   [".","9","8",".",".",".",".","6","."],   ["8",".",".",".","6",".",".",".","3"],   ["4",".",".","8",".","3",".",".","1"],   ["7",".",".",".","2",".",".",".","6"],   [".","6",".",".",".",".","2","8","."],   [".",".",".","4","1","9",".",".","5"],   [".",".",".",".","8",".",".","7","9"] ] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid. Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules. The given board contain only digits  1-9  and the character  '.' . The given board size is always  9x9 .

判斷一個 9x9 的數獨是否有效。隻需要根據以下規則，驗證已經填入的數字是否有效即可。 數字  1-9  在每一行隻能出現一次。 數字  1-9  在每一列隻能出現一次。 數字  1-9  在每一個以粗實線分隔的  3x3  宮内隻能出現一次。 上圖是一個部分填充的有效的數獨。 數獨部分空格内已填入了數字，空白格用  '.'  表示。 示例 1: 輸入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 輸出: true 示例 2: 輸入: [   ["8","3",".",".","7",".",".",".","."],   ["6",".",".","1","9","5",".",".","."],   [".","9","8",".",".",".",".","6","."],   ["8",".",".",".","6",".",".",".","3"],   ["4",".",".","8",".","3",".",".","1"],   ["7",".",".",".","2",".",".",".","6"],   [".","6",".",".",".",".","2","8","."],   [".",".",".","4","1","9",".",".","5"],   [".",".",".",".","8",".",".","7","9"] ] 輸出: false 解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格内其他數字均與 示例1 相同。 但由于位于左上角的 3x3 宮内有兩個 8 存在, 是以這個數獨是無效的。 說明: 一個有效的數獨（部分已被填充）不一定是可解的。 隻需要根據以上規則，驗證已經填入的數字是否有效即可。 給定數獨序列隻包含數字  1-9  和字元  '.'  。 給定數獨永遠是  9x9  形式的。

思路：數獨每行每列每個格子 都不重複。定義三個标記的存儲空間。周遊每一個元素的時候判斷它在行列或格子是否重複。重複則傳回false。這裡需要一個将格子位置轉換：[3*(i/3)+j/3][n]，表示 将原始數組i和j 坐标轉化為 第幾個格子的坐标。

注意c++定義二維m行n列的bool數組可以一句話搞定vector<vector<bool>> rowflag(m,vector<bool>(n,false));

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int m=board.size(),n=board[0].size();
        if(m==0 || n==0) return false;
        vector<vector<bool>> rowflag(m,vector<bool>(n,false));
        vector<vector<bool>> colflag(m,vector<bool>(n,false));
        vector<vector<bool>> cellflag(m,vector<bool>(n,false));
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(board[i][j]<='9' && board[i][j]>='1')
                {
                    int tmp = board[i][j]-'1';
                    if(rowflag[i][tmp] || colflag[tmp][j] ||
                      cellflag[3*(i/3)+j/3][tmp])
                        return false;
                    rowflag[i][tmp]=true;
                    colflag[tmp][j]=true;
                    cellflag[3*(i/3)+j/3][tmp] = true;
                }
            }
        }
        return true;
    }
};
           

class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row= [[0]*9 for _ in range(9)]
        col= [[0]*9 for _ in range(9)]
        cell= [[0]*9 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                if(board[i][j]<='9' and board[i][j]>='1'):
                    n = int(board[i][j])-1
                    pos = 3*int(i/3)+int(j/3)
                    if row[i][n]!=0 or col[n][j]!=0 or cell[pos][n]!=0:
                        return False
                    row[i][n]=1
                    col[n][j]=1
                    cell[pos][n]=1
        return True