Source: Valid Sudoku

Determine if a Sudoku is valid, according to: http://sudoku.com.au/TheRules.aspx

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

The input corresponding to the above configuration :

["53..7....", 
 "6..195...",
 ".98....6.",
 "8...6...3",
 "4..8.3..1",
 "7...2...6",
 ".6....28.",
 "...419..5",
 "....8..79"]

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.

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

解題：

  1. 看到又是數獨相關題目，背脊不自覺涼了一下。幸好這題跟上次寫的比起來僅是初階版本，只需要驗證輸入值給的數獨矩陣是否有效（但不一定可解，意思是數獨矩陣的輸入值符合數獨矩陣成立之定義：每行不存在重複、每列不存在重複、以及九宮格內部存在重複。符合以上條件之輸入值不代表該數獨矩陣一定有解。）；
  2. 因此要執行相關驗證，便需要相關行列及九宮格在迴圈執行過程中存取相關資訊，一個方法是使用陣列值存取，但其最大問題就是在驗證過程中需要再執行 (if i in L) 這樣的迴圈程序。此時便可採用 hashmap 來建立對應值，而驗證過程只須視相對應的字典中是否已存在該對應值，如有即表示存在數字重複出現，該數獨矩陣必不成立；
  3. 而在實際面試過程中，依據題目給的資料亦需要測試一些極端值或不合規格之資料，像這題筆者在進行數獨矩陣輸入值的測試時便發現，在輸入資料包含 0 以及行列長度超過 9 的情況下該數獨矩陣仍可以被定義為有效，實際面試時如遇到這題則需要另外注意並與面試人員釐清相關條件限制。

Code:

from collections import defaultdict
class Solution:
    # @param A : tuple of strings
    # @return an integer
    def isValidSudoku(self, A):
        rows = defaultdict(dict)
        columns = defaultdict(dict)
        matrixes = defaultdict(dict)
        for i in range(9):
            for j in range(9):
                if A[i][j] == ".": continue
                try:
                    if rows[i][A[i][j]]: return 0
                except:
                    rows[i][A[i][j]] = True
                try:
                    if columns[j][A[i][j]]: return 0
                except:
                    columns[j][A[i][j]] = True
                try:
                    if matrixes[i//3*3+j//3][A[i][j]]: return 0
                except:
                    matrixes[i//3*3+j//3][A[i][j]] = True
        return 1

GitHub: GitHub

發表留言