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

pic

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.

解题方法

首先要把sudoku的规则记住

  • 9行9列
  • 每行只能有1-9，不能重复
  • 每列只能有1-9，不能重复
  • 有9个小的3*3的sub-box, 它们中也只能有1-9，不能重复

解题方法

  • 用三个2-D array保存row, column, sub sodoku里面已经用过的value
  • 遍历每一个格子，检查是否valid

注意点

  • 建立的array是0-based的，所以1-9的数字放在array里是要减去1
  • sub sodoku位置的计算，可以规定排列为
0 1 2 
3 4 5 
6 7 8

那么根据row和col得到的所属的sub sodoku公式就是(row / 3) * 3 + col / 3

Solution

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        if not list:
            return False
        rowValid = [[False for i in range(9)] for j in range(9)]
        colValid = [[False for i in range(9)] for j in range(9)]
        subValid = [[False for i in range(9)] for j in range(9)]

        row = len(board)
        col = len(board[0])
        for i in range(row):
            for j in range(col):
                if board[i][j] == ".":
                    continue
                value = int(board[i][j]) - 1
                if rowValid[i][value]:
                    return False
                if colValid[j][value]:
                    return False
                subNum = (i / 3) * 3 + j / 3
                if subValid[subNum][value]:
                    return False
                rowValid[i][value] = True
                colValid[j][value] = True
                subValid[subNum][value] = True
        return True

Reference