Day 10 - Valid Sudoku

13th鐵人賽

毛毛

團隊Weeeeeeeeeeeeeeeeeee

2021-09-25 00:41:30

1579 瀏覽

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題Day~

tags: `2021_iThome鐵人賽` `Leetcode`

36. Valid Sudoku

Question

Determine if a 9 x 9 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 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

Example1

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

Example2

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 '.'.

解題

題目

首先先簡單的翻譯一下題目
~~給一個數獨題目要你解~~，給一個數獨題目要判斷這個數獨題目是不是合乎數獨的規則，也就是不管是行、列和9塊3 x 3的區塊，出現的數字1-9皆不能重複。

Think

作法大致上是這樣

本來一開始是打算用for loop做，但是忽然想到有enumerate可以使用，enumerate有點像for rowVal in board:的方式，只是每個值會在額外配上一個sequence，這個sequence的起始可以透過start參數來決定。
因為有行、列和區塊要判斷，所以就分三個部份分別處理。
下面避免行列混淆，用Row跟Column來說明。
Row part & Column part
- 由row和col這兩個list存著已經出現過的值，假如新讀到的值已經有存在裡頭了，就代表重複了，回傳False；沒有的話，就存入。
- 存入的值為(seq, value)搭配
subBox part
- 由subBox這個list存著已經出現過的值，假如新讀到的值已經有存在裡頭了，就代表重複了，回傳False；沒有的話，就存入。
- 存入的值是取seq/3的商，這邊我用轉int把小數部分捨去了。
- 這樣可以得到9個區塊分別的代碼：
  - 0,0、0,1、0,2
  - 1,0、1,1、1,2
  - 2,0、2,1、2,2
- 在配上每個點的value就可以透過subBox的list判斷有沒有重複數字了。
C的程式出了點問題QQ，再補上。

Code

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = []
        col = []
        subBox = []
        
        for seq1, rowVal in enumerate(board, start=0):
            for seq2, colVal in enumerate(rowVal, start=0):

                if colVal is not ".":
                    # Row part
                    if (seq1, colVal) not in row:
                        row.append((seq1, colVal))
                    else:
                        return False

                    # Column part
                    if (seq2, colVal) not in col:
                        col.append((seq2, colVal))
                    else:
                        return False
                
                    # subBox part
                    if (int(seq1/3), int(seq2/3), colVal) not in subBox:
                        subBox.append((int(seq1/3), int(seq2/3), colVal))
                    else:
                        return False
        return True