Valid Sudoku

Patrick Leaton
Published: Aug. 3, 2021, 8:06 a.m.
Problem Description

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

 

 

The description is taken from https://leetcode.com/problems/valid-sudoku/.

Problem Solution

#O(N^2) Time, O(N^2) Space
#Technically constant though since fixed length.
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows,cols,squares = {},{},{}
        for row in range(0,9):
            for col in range(0,9):
                value = board[row][col]
                square = (row//3, col//3)
                if value == ".":
                    continue
                if row not in rows:
                    rows[row] = set()
                if col not in cols:
                    cols[col] = set()
                if square not in squares:
                    squares[(row//3, col//3)] = set()
                if (value in rows[row] or
                    value in cols[col] or
                    value in squares[square]):
                    return False
                rows[row].add(value)
                cols[col].add(value)
                squares[square].add(value)
        return True

 

Problem Explanation

In this problem, we don't actually have to solve the Sudoku board.  

We just need to return whether it is valid or not, that makes it easy for us.

To validate something, we can run tests trying to invalidate it.  If it doesn't fail the tests, we have validated it.

Given the rows and the constraints, we basically just have to check if there are repeating digits in the boxes.  Each row and column must have unique characters so we can have two pointers that iterate through each row and column.  We can have a hashmap to check if we have a duplicate in the current row or column by utilizing these pointers.  

The three-by-three square requiring unique digits is the real trick of this problem.  However, we can just do the same thing we are doing for the rows and columns, but divide the row and column pointers by three.  By doing this, we are separating the rows and columns one through nine into nine squares. These squares are what will go in the hashmap.

Let's start by creating a hashmap for the board's rows, squares, and columns to check for duplicates.

        rows,cols,squares = {},{},{}
 

 

Next, we will iterate through the rows and columns of the nine-by-nine board.

        for row in range(0,9):
            for col in range(0,9):

 

Let's track the current cell of the board with a value variable.

                value = board[row][col]
 

 

We will also track the current square.  

The rows and columns divided by three will make them fall into one of these nine boxes.

                square = (row//3, col//3)
 

0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,1 2,2

 

If the current value is blank, we can just move on because we don't need to validate this cell.  Remember, we aren't trying to solve the Sudoku board, we just need to validate it.

                if value == ".":
                    continue

 

If that is not the case, we will see if this is the first time we have visited this row, column, or square.  

If it is, we will initialize the row, column, and square in their respective hashmaps with a set so that we can have constant lookup time to see if there are duplicates.

                if row not in rows:
                    rows[row] = set()
                if col not in cols:
                    cols[col] = set()
                if square not in squares:
                    squares[(row//3, col//3)] = set()

 

Now, we will see if the current value has already been used in the current row, column, or square, and we will be returning false if it was.

                if (value in rows[row] or
                    value in cols[col] or
                    value in squares[square]):
                    return False

 

If not, this is a valid value so far so we will add it to each set in each hashmap.

                rows[row].add(value)
                cols[col].add(value)
                squares[square].add(value)

 

If we reach the end of the board and haven't invalidated any cells, we have a valid board.

        return True