Teaching Kids Programming – Sudoku Validator/Algorithm using 27 Hash Sets

Teaching Kids Programming: Videos on Data Structures and Algorithms

Sudoku is a puzzle where you’re given a 9 by 9 grid with digits. The objective is to fill the grid with the constraint that every row, column, and box (3 by 3 subgrid) must contain all of the digits from 1 to 9, and numbers shouldn’t repeat within a row, column, or box.

Given a filled out sudoku board, return whether it’s valid.

Constraints
n = 9 where n is number of rows and columns in matrix
Example 1
Input

1 2 3 4 5 6 7 8 9 10 11

matrix = [     [4, 2, 6, 5, 7, 1, 3, 9, 8],     [8, 5, 7, 2, 9, 3, 1, 4, 6],     [1, 3, 9, 4, 6, 8, 2, 7, 5],     [9, 7, 1, 3, 8, 5, 6, 2, 4],     [5, 4, 3, 7, 2, 6, 8, 1, 9],     [6, 8, 2, 1, 4, 9, 7, 5, 3],     [7, 9, 4, 6, 3, 2, 5, 8, 1],     [2, 6, 5, 8, 1, 4, 9, 3, 7],     [3, 1, 8, 9, 5, 7, 4, 6, 2] ]

matrix = [
    [4, 2, 6, 5, 7, 1, 3, 9, 8],
    [8, 5, 7, 2, 9, 3, 1, 4, 6],
    [1, 3, 9, 4, 6, 8, 2, 7, 5],
    [9, 7, 1, 3, 8, 5, 6, 2, 4],
    [5, 4, 3, 7, 2, 6, 8, 1, 9],
    [6, 8, 2, 1, 4, 9, 7, 5, 3],
    [7, 9, 4, 6, 3, 2, 5, 8, 1],
    [2, 6, 5, 8, 1, 4, 9, 3, 7],
    [3, 1, 8, 9, 5, 7, 4, 6, 2]
]

Output
True

Algorithm to Validate a Sudoku Game Board/State

A valid Sudoku Board should have only digit from 1 to 9 only once in each row (9 rows), each column (9 columns) and 9 sub-3×3 grids. We can use 27 hash sets to store the numbers that we have seen and invalidate the Sudoku immediately once we find out the current number in the cell has appeared before. Also, we have to make sure the digit is strictly between 1 to 9 inclusive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def validSudokuGame(self, matrix):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [[set() for _ in range(3)] for _ in range(3)]
        for r in range(9):
            for c in range(9):
                x = matrix[r][c]
                if x < 1 or x > 9:
                    return False
                if x in rows[r]:
                    return False
                if x in cols[c]:
                    return False
                if x in boxes[r//3][c//3]:
                    return False
                rows[r].add(x)
                cols[c].add(x)
                boxes[r//3][c//3].add(x)
        return True

class Solution:
    def validSudokuGame(self, matrix):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [[set() for _ in range(3)] for _ in range(3)]
        for r in range(9):
            for c in range(9):
                x = matrix[r][c]
                if x < 1 or x > 9:
                    return False
                if x in rows[r]:
                    return False
                if x in cols[c]:
                    return False
                if x in boxes[r//3][c//3]:
                    return False
                rows[r].add(x)
                cols[c].add(x)
                boxes[r//3][c//3].add(x)
        return True

Then, if this number in this cell does not violate 3 rules, we add it to 3 hash sets. The time and space complexity is O(1) constant as the size of the board is fixed.

See also: Depth First Search (Backtracking) Algorithm to Solve a Sudoku Game

–EOF (The Ultimate Computing & Technology Blog) —