Sudoku Brute Forcer. Uses recursion to test every possible valid combination of numbers until a solution is found. Can solve human-unsolvable sudokus.

sudoku-solver.py

'''
Example usage:
grid = [
    [7,0,0,  0,0,9,  0,0,0],
    [0,0,0,  6,0,0,  0,4,0],
    [0,0,2,  0,0,0,  0,0,0],

    [0,0,0,  0,0,0,  4,0,0],
    [0,5,0,  0,4,6,  0,0,0],
    [0,0,0,  0,0,0,  0,0,0],

    [0,0,6,  0,0,0,  0,0,5],
    [2,0,0,  5,0,0,  0,0,0],
    [0,0,0,  0,0,0,  0,3,0]
]

sudoku_solver(grid)
'''

import numpy as np

def sudoku_is_valid(grid):
    # Is the grid even a list?
    if not isinstance(grid, list):
        return False

    # Check if the array is 9x9
    if len(grid) != 9:
        return False
    if len(grid[0]) != 9:
        return False

    # Check every row is 9 elements long
    for row in grid:
        if len(row) != 9:
            return False

    return True


def revise_candidates(grid, candidates):
    # Candidates is a dictionary with tuples as keys
    # We use is_valid to check if a candidate is valid
    # Then fill them all in
    for i in range(9):
        for j in range(9):
            candidate_list = []
            tuple_key = (i, j)
            for k in range(1, 10):
                if is_valid(grid, k, i, j):
                    candidate_list.append(k)

            candidates[tuple_key] = candidate_list


def find_empty_cell(grid):
    # Find the first available empty cell
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                return i, j
    return None


def is_valid(grid, num, row, col):
    # Check row
    if num in grid[row]:
        return False

    # Check column
    if num in grid[:, col]:
        return False

    # Check box
    box_row = (row // 3) * 3
    box_col = (col // 3) * 3
    if num in grid[box_row:box_row + 3, box_col:box_col + 3]:
        return False

    return True


def solve_sudoku(grid):
    candidates = {}

    revise_candidates(grid, candidates)

    empty_cell = find_empty_cell(grid)
    if empty_cell is None:
        return True

    row, col = empty_cell

    for num in candidates[(row, col)]:
        grid[row][col] = num

        if solve_sudoku(grid):
            return True

        grid[row][col] = 0

    return False


def sudoku_solver(grid):
    if not sudoku_is_valid(grid):
        return "invalid grid"

    grid = np.array(grid)

    if solve_sudoku(grid):
        print("Solution:")
        print(grid)
    else:
        print("No solution found.")

    return grid