5 Best Ways to Validate if a Sudoku Grid is Solvable in Python

by

💡 Problem Formulation: Sudoku, a logic-based combinatorial number-placement puzzle, intrigues minds globally. Ensuring a grid is solvable is crucial to a satisfying experience. This article presents various Python methods to validate the solvability of a given Sudoku grid, laying out inputs as a 9×9 list of lists—with each inner list representing a Sudoku row—and outputs as a boolean value indicating solvability.

Method 1: Backtracking Algorithm

A backtracking algorithm tries to solve the Sudoku by filling in digits one by one. It checks the constraints of Sudoku with each insertion and if the insertion breaks the rule, it backtracks and tries the next digit. This method is comprehensive as it mimics the manual solving approach.

Here’s an example:

def is_valid(bo, num, pos):
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False
    # Check column and 3x3 square
    return True  # omitted for brevity
# Solve function with backtracking
def solve(bo):
    # Solving code omitted for brevity
    return True if some_condition else False

Output:

True or False

The is_valid() function checks if a number can be placed in a given position, and the solve() function utilises backtracking to fill the board and determine solvability. It returns True if the Sudoku can be solved and False otherwise.

Method 2: Constraint Propagation

Constraint propagation narrows the possible values for each empty cell before attempting a search. This method uses known constraints to reduce the number of choices available, making the solution process faster than brute force backtracking alone.

Here’s an example:

def reduce_puzzle(bo):
    # Reduction code omitted for brevity
    return bo, True
def solve(bo):
    # Combine reduction with backtracking omitted for brevity
    return True if solved else False

Output:

True or False

The reduce_puzzle() function iteratively applies constraints to narrow down options, and the solve() function mixes this approach with backtracking to find a solution, if one exists.

Method 3: Stochastic Search

Stochastic search uses a form of trial and error that is partly randomised. It assigns numbers randomly in empty positions and uses a fitness function to score how close the grid is to a solution. It then improves upon this iteratively. This method doesn’t guarantee solvability, but can often quickly find a solution where one is difficult to detect.

Here’s an example:

import random
def fitness(bo):
    # Fitness calculation code omitted for brevity
    return fitness_score
# Stochastic solve function
def stoch_solve(bo):
    # Stochastic solving code omitted for brevity
    return True if solved else False

Output:

True or False

The code shows the structure of a stochastic solver, using fitness() to evaluate the current state of the grid, and stoch_solve() to modify the grid randomly, improving the solution iteratively.

Method 4: Exact Cover Problem and Algorithm X

Every Sudoku puzzle can be represented as an Exact Cover problem and solved using Algorithm X, also known as Dancing Links. This method translates Sudoku constraints into an exact cover matrix and recursively selects rows from this matrix that satisfy the constraints.

Here’s an example:

def solve(bo):
    # Transform, solve with Algorithm X, and transform back code omitted for brevity
    return True if solved else False

Output:

True or False

This code snippet illustrates a high-level view of the Exact Cover to Sudoku problem transformation and the application of Algorithm X to find a solution.

Bonus One-Liner Method 5: Python Libraries

Python has several libraries that can validate and solve Sudoku puzzles. Libraries like py-sudoku or sudoku-solver implement the above methods internally and provide a clean interface to check solvability.

Here’s an example:

from sudoku import Sudoku
puzzle = Sudoku(board)
print(puzzle.is_solvable())

Output:

True or False

This one-liner uses the Sudoku class from a Sudoku-specific library to create a puzzle object and then simply calls its is_solvable() method to determine if the grid can be solved.

Summary/Discussion

  • Method 1: Backtracking. Highly reliable. Can be slow for complex grids.
  • Method 2: Constraint Propagation. Efficient solver. May not handle extremely difficult puzzles.
  • Method 3: Stochastic Search. Fast approximations. No solvability guarantee.
  • Method 4: Exact Cover and Algorithm X. Elegant and powerful. Complexity in implementation.
  • Method 5: Python Libraries. Simplifies code. Reliant on library quality and updates.