LeetCode: 36-Valid Sudoku 解題紀錄

Last Updated on 2022-11-23 by Clay

題目

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

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.

Example 1:

Input: board = 
[["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: board = 
[["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.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

本題是驗證一個數獨題目的有效性。老實說如果要驗證數獨題目的有效性應該再加上至少要有 17 個已填充的數值才能保證唯一解… 不過解題就是解題，題目的設定說了算。

基本上就是無論縱橫、九宮格內，數值一定都必須能夠填入 1-9。這意味著只要在發現有數值重複出現了，就代表這是一個無效的數獨題目。

---

解題思路

我使用的是比較很直接的解法。分別設定三個函數，在每次碰到數字時，分別判斷行、列、九宮格中是否出現同樣的數字（當然得排除自己）。

C++ 範例程式碼

class Solution {
public:
    bool rowCollision(vector<vector<char>>& board, int i, int j) {
        for (int k=0; k<board.size(); ++k) { 
            if (k != j && board[i][k] == board[i][j]) return true;
        }
        return false;
    }
    
    bool colCollision(vector<vector<char>>& board, int i, int j) {
        for (int k=0; k<board.size(); ++k) {
            if (k !=i && board[k][j] == board[i][j]) return true;
        }
        return false;
    }
    
    bool gridCollision(vector<vector<char>>& board, int i, int j) {
        int si = i / 3 * 3;
        int ei = i / 3 * 3 + 3;
        int sj = j / 3 * 3;
        int ej = j / 3 * 3 + 3;
        
        for (int temp_i=si; temp_i<ei; ++temp_i) {
            for (int temp_j=sj; temp_j<ej; ++temp_j) {
                if (temp_i == i && temp_j == j) continue;
                if (board[temp_i][temp_j] == board[i][j]) return true;
            }
        }
        
        return false;
    }
    
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i=0; i<board.size(); ++i) {
            for (int j=0; j<board.size(); ++j) {
                if (board[i][j] == '.') continue;
                if (rowCollision(board, i, j) ||
                    colCollision(board, i, j) ||
                    gridCollision(board, i, j)) {
                    return false;
                }
            }
        }

        return true;
    }
};

Python 範例程式碼

class Solution:
    def rowCollision(self, board: List[List[str]], i: int, j: int) -> bool:
        for k in range(len(board)):
            if k != j and board[i][k] == board[i][j]:
                return True
        return False
    
    def colCollision(self, board: List[List[str]], i: int, j: int) -> bool:
        for k in range(len(board)):
            if k != i and board[k][j] == board[i][j]:
                return True
        return False
    
    def gridCollision(self, board: List[List[str]], i: int, j: int) -> bool:
        si = i // 3 * 3
        ei = i // 3 * 3 + 3
        sj = j // 3 * 3
        ej = j // 3 * 3 + 3
        
        for temp_i in range(si, ei):
            for temp_j in range(sj, ej):
                if temp_i == i and temp_j == j: 
                    continue
                if board[temp_i][temp_j] == board[i][j]:
                    return True
        return False
    
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(len(board)):
            for j in range(len(board)):
                if board[i][j] == ".":
                    continue
                if self.rowCollision(board, i, j) or self.colCollision(board, i, j) or self.gridCollision(board, i, j):
                    return False
        return True

---

References

• 36. Valid Sudoku

---

Read More

• LeetCode 解題紀錄目錄