How to Detect a Valid Sudoku Board in Python

Sudoku is a popular number placement puzzle that has gained widespread popularity worldwide. The objective of the game is to fill a 9x9 grid with digits from 1 to 9 such that each row, column, and 3x3 sub-grid contains all of the digits from 1 to 9.

In this comprehensive Python programming guide, we will examine step-by-step how to write a program that can determine if a given Sudoku board is valid by checking if it satisfies the fundamental Sudoku rules of no repeated digits in rows, columns, or 3x3 sub-grids.

Table of Contents

Overview

Here are the key things we will cover in this how-to guide:

• Understanding the Sudoku validation problem
• Sudoku rules that define a valid board
• General approach to detect a valid Sudoku board
• Implementing the solution in Python
  • Reading board input
  • Checking rows
  • Checking columns
  • Checking sub-grids
• Example valid and invalid Sudoku boards
• Complete runnable Python code solution with explanations

By the end, you will have a clear understanding of how to check if a Sudoku board is valid using Python. The concepts and techniques covered can serve as a great learning exercise for honing your Python skills and logic development.

Prerequisites

To follow this Sudoku validity checker tutorial, you should have:

• Basic Python programming knowledge
• Familiarity with basic data structures like lists, tuples, and dictionaries
• Understanding of nested loops and conditionals

Optionally, knowledge of functions, recursion, and object-oriented programming can aid comprehension but is not mandatory. The complete code solution works with Python 3.

Understanding the Sudoku Validation Problem

Before we code up a solution, it’s important to first understand the problem we are trying to solve.

The 9x9 Sudoku board can be represented in Python as a 9x9 list or 2D array containing integers from 1 to 9. Some cells may be blank which we can represent with a 0 value.

A valid Sudoku board satisfies these rules:

1. Each row must contain the digits from 1 to 9 exactly once.
2. Each column must contain the digits from 1 to 9 exactly once.
3. Each 3x3 sub-grid must contain the digits from 1 to 9 exactly once.

Our goal is to write a Python program that accepts a 9x9 Sudoku board as input, iterates through the board structure, and returns True if the board is valid, or False if it is invalid by breaking any of the above rules.

This is a classic constraint satisfaction problem (CSP) where we check if all the constraints or Sudoku rules are satisfied to classify the board as valid or invalid.

General Approach

We can outline a high-level approach to solve this problem as follows:

1. Read the 9x9 Sudoku board input in a 2D array structure
2. Iterate through each row and check if it contains digits 1 to 9 exactly once.
3. Iterate through each column and check if it contains digits 1 to 9 exactly once.
4. Iterate through each 3x3 sub-grid and check if it contains digits 1 to 9 exactly once.
5. If all the above conditions are satisfied, return True.
6. If any condition fails, return False.

The key steps are iterating through the various row, column and grid sections efficiently and checking that the digits 1 to 9 occur exactly once in each section.

Now let’s code this up in Python step-by-step.

Implementing the Valid Sudoku Checker in Python

We will structure our Python Sudoku validity checker solution into four key parts:

1. Sudoku board input
2. Check rows
3. Check columns
4. Check 3x3 sub-grids

Let’s look at each section.

1. Read Sudoku Board Input

We first need to read the 9x9 Sudoku board in a structure we can traverse easily in Python.

A 9x9 list or 2D array is ideal for this. Here is an example valid Sudoku board input:

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

We can read this into a Python list like:

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

This represents our Sudoku board data structure which we can now traverse to implement our checks.

2. Check Rows

To check rows, we need to iterate from 0 to 9 rows and in each row iterate from 0 to 9 columns and check if it contains digits from 1 to 9 exactly once using a set.

# Check rows
for row in range(9):
    row_set = set()
    for col in range(9):
        curr = board[row][col]
        if curr != 0:
            if curr in row_set:
                return False
            row_set.add(curr)

return True

Here we iterate each row, populate a set with non-zero digits encountered and return False if we see any digit more than once indicating duplicate digits in the row.

If we get through all rows successfully, we return True.

3. Check Columns

Similar to rows, we need to traverse columns in the range 0 to 9 and check if each column contains digits 1 to 9 exactly once:

# Check columns
for col in range(9):
    col_set = set()
    for row in range(9):
        curr = board[row][col]
        if curr != 0:
            if curr in col_set:
                return False
            col_set.add(curr)

return True

This checks each column linearly and returns False if a duplicate digit is found. Otherwise, we return True after iterating all columns.

4. Check 3x3 Sub-Grids

To check each 3x3 sub-grid, we need nested loops traversing rows 0,1,2 then 3,4,5 and 6,7,8 and similarly for columns 0,1,2 , 3,4,5 and 6,7,8 to cover all 9 sub-grids.

# Check sub-grids
for row in (0, 3, 6):
    for col in (0, 3, 6):
        grid_set = set()
        for r in range(row, row + 3):
            for c in range(col, col + 3):
                curr = board[r][c]
                if curr != 0:
                    if curr in grid_set:
                        return False
                    grid_set.add(curr)

return True

This ensures we check each 3x3 grid section thoroughly.

Putting it Together

The complete Sudoku validity checker code looks like:

# Check if a Sudoku board is valid

def isValidSudoku(board):

    # Check rows
    for row in range(9):
        row_set = set()
        for col in range(9):
            curr = board[row][col]
            if curr != 0:
                if curr in row_set:
                    return False
                row_set.add(curr)

    # Check columns
    for col in range(9):
        col_set = set()
        for row in range(9):
            curr = board[row][col]
            if curr != 0:
                if curr in col_set:
                    return False
                col_set.add(curr)

    # Check 3x3 sub-grids
    for row in (0, 3, 6):
        for col in (0, 3, 6):
            grid_set = set()
            for r in range(row, row + 3):
                for c in range(col, col + 3):
                    curr = board[r][c]
                    if curr != 0:
                        if curr in grid_set:
                            return False
                        grid_set.add(curr)

    # All checks passed
    return True

This complete function first checks rows, then columns, then 3x3 sub-grids using the logic discussed above.

It returns True only if all checks are cleared, else returns False if any check fails indicating an invalid Sudoku board.

Testing the Validator on Sample Boards

Let’s test our Sudoku solution on some sample boards to verify it correctly detects valid and invalid boards.

Example 1: Valid Board

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

print(isValidSudoku(board1)) # True

This prints True as expected.

Example 2: Invalid Board

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

print(isValidSudoku(board2)) # False

This is invalid because the 3rd row contains two 6’s. Our program correctly prints False.

The complete code with these test cases is provided in the next section.

Complete Python Code for Valid Sudoku Checker

Here is the complete runnable Python code for detecting a valid Sudoku board:

# Sudoku Validity Checker

# Check if a Sudoku board is valid
def isValidSudoku(board):

    # Check rows
    for row in range(9):
        row_set = set()
        for col in range(9):
            curr = board[row][col]
            if curr != 0:
                if curr in row_set:
                    return False
                row_set.add(curr)

    # Check columns
    for col in range(9):
        col_set = set()
        for row in range(9):
            curr = board[row][col]
            if curr != 0:
                if curr in col_set:
                    return False
                col_set.add(curr)

    # Check 3x3 sub-grids
    for row in (0, 3, 6):
        for col in (0, 3, 6):
            grid_set = set()
            for r in range(row, row+3):
                for c in range(col, col+3):
                    curr = board[r][c]
                    if curr != 0:
                        if curr in grid_set:
                            return False
                        grid_set.add(curr)

    # All checks passed
    return True


# Test cases

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

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

print(isValidSudoku(board1))
print(isValidSudoku(board2))

When executed, this correctly prints:

True
False

This covers the key techniques to check if a given Sudoku board is valid or invalid in Python by verifying it satisfies the fundamental Sudoku rules.

Summary

In this comprehensive how-to guide, we looked at how to detect a valid Sudoku board in Python step-by-step:

• Understood the constraints that define a valid Sudoku board
• Discussed a general approach to traverse the board structure and validate rules
• Implemented the solution traversing rows, columns and sub-grids
• Tested the validator program on sample valid and invalid boards
• Provided a complete runnable Python code solution

Key takeaways include:

• Representing the board as a 9x9 2D list
• Using linear iteration and sets to check rows and columns
• Nested loops to traverse 3x3 sub-grids
• Returning True if all checks pass, False otherwise

This serves as a good programming exercise to apply Python fundamentals like loops, functions, lists, sets and conditionals.

The techniques can be extended to solve the actual Sudoku puzzle using backtracking, recursion or constraint solving. But validity checking is an important first step.

This guide should provide you a clear understanding of how to detect a valid Sudoku board in Python. The concepts can help build your proficiency in Python and logical reasoning skills.

Happy coding!