36. Valid Sudoku

27 Dec 36. Valid Sudoku

Posted at 18:29h in Coding by
0 Likes

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

 

To solve this problem we have to check if each value in sudoku does not repeat in its:

  1. column
  2. row
  3. square

To do this efficiently we will use sets to store elements in columns, rows and squares. This is easy to define column and row (by single index), but squares are defined using two indexes. We will use // (floor division) operator to know in which square we are right now.

Indexes range from 0 to 8.
0 // 3 = 0
1 // 3 = 0
2 // 3 = 0
3 // 3 = 1
4 // 3 = 1
5 // 3 = 1
6 // 3 = 2
7 // 3 = 2
8 // 3 = 2

We got 3 different values for each range (0-2: 0, 3-5: 1, 6-8: 2), so we can use it to know in which square are currently are (by getting square x and y coordinate, we need 9 squares with indexes (0, 0), (0, 1), (0, 2), (1,0), …, (2, 2)).

In code we do nothing if we meet . symbol, but if we have digit in cell, then we check if it is in cell’s row, column or square.
If yes, then it means that the value is repeated, so sudoku is not valid one, so we return False.

After checking, we add this value to its row, column and square.
If number occurs 2 times in given row, cell or square, then the 2nd occurence is going to trigger False return (because in first occurence we add the value to the sets).

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for x in range(9)]
        columns = [set() for x in range(9)]
        squares = [[set() for x in range(3)] for y in range(3)]
        for i in range(9):
            for j in range(9):
                cell_value = board[i][j]
                if cell_value == “.”:
                    continue
                if cell_value in rows[i] or cell_value in columns[j] or cell_value in squares[i//3][j//3]:
                    return False
               
                rows[i].add(cell_value)
                columns[j].add(cell_value)
                squares[i//3][j//3].add(cell_value)
       
        return True

 

No Comments

Post A Comment