Solving Sudoku with Algebraic Geometry

Introduction: Sudoku and Mathematics #

Sudoku is a popular logic puzzle with simple rules. Each row, column, and 3×3 box in a 9×9 grid must contain the digits 1 through 9 exactly once. These puzzles are often solved through trial and error or more systematic backtracking algorithms.

But what if we modeled Sudoku using more abstract mathematics, such as algebraic geometry? This article explores how to turn Sudoku constraints into polynomial equations and use computer algebra to approach the puzzle differently. We will also look at a practical Python solver alongside the theoretical model.

Turning Sudoku Rules into Polynomials #

The basic idea is to represent each of the 81 cells with a variable x_i, where i runs from 1 to 81. We want a system of equations that forces those variables to obey the rules.

The Algebraic Model: Ideals and Varieties #

An ideal brings the polynomial constraints together. We work over a field K, typically the rational or complex numbers, with polynomial variables for the cells and the auxiliary variables introduced above.

The ideal I is generated by all the value-constraint polynomials F_i(x_i) and the uniqueness polynomials y_ij * (x_i - x_j) - 1 for pairs in E.

The common zero set of these polynomials is the variety V(I). Its cell coordinates (x_1, ..., x_81) satisfy the Sudoku rules. The digit constraints already restrict those coordinates to the integers 1 through 9.

Solving a Particular Puzzle #

A Sudoku puzzle begins with some cells filled in. Let L be the subset of cell indices for which an initial value a_i is given. Add these clues to the model by adjoining the equations x_i - a_i = 0 for every i in L. Call the resulting ideal I_S.

For a puzzle with a unique solution, the cell-coordinate part of the reduced Gröbner basis takes the form:

{x_1 - a_1, x_2 - a_2, ..., x_81 - a_81}

The auxiliary variables also have determined values in the extended system.

Gröbner bases are powerful tools for solving polynomial systems and can be computed with computer algebra systems.

Theory and Practice: Computational Cost #

This algebraic approach is elegant, but computing a Gröbner basis for a system with 81 cell variables is computationally expensive. In practice, much more efficient Sudoku-solving methods are available.

One of the most common is backtracking.

A Practical Approach: Backtracking in Python #

Here is a simple Python program using standard backtracking:

1
N = 9
2
EMPTY = 0
3

4
def print_board(board):
5
    print("-------------------------")
6
    for i in range(N):
7
        print("| ", end="")
8
        for j in range(N):
9
            print(". " if board[i][j] == EMPTY else f"{board[i][j]} ", end="")
10
            if (j + 1) % 3 == 0:
11
                print("| ", end="")
12
        print()
13
        if (i + 1) % 3 == 0:
14
            print("-------------------------")
15

16
def is_valid(board, row, col, num):
17
    if num in board[row]:
18
        return False
19
    if num in [board[i][col] for i in range(N)]:
20
        return False
21
    start_row, start_col = row - row % 3, col - col % 3
22
    for i in range(3):
23
        for j in range(3):
24
            if board[i + start_row][j + start_col] == num:
25
                return False
26
    return True
27

28
def find_empty_cell(board):
29
    for row in range(N):
30
        for col in range(N):
31
            if board[row][col] == EMPTY:
32
                return row, col
33
    return None
34

35
def solve_sudoku(board):
36
    cell = find_empty_cell(board)
37
    if cell is None:
38
        return True
39
    row, col = cell
40
    for num in range(1, 10):
41
        if is_valid(board, row, col, num):
42
            board[row][col] = num
43
            if solve_sudoku(board):
44
                return True
45
            board[row][col] = EMPTY
46
    return False
47

48
if __name__ == "__main__":
49
    board = [
50
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
51
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
52
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
53
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
54
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
55
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
56
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
57
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
58
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
59
    ]
60
    print("Initial Sudoku:")
61
    print_board(board)
62
    print("\nSolving...\n")
63
    if solve_sudoku(board):
64
        print("Solved Sudoku:")
65
        print_board(board)
66
    else:
67
        print("No solution found.")

The algorithm finds an empty cell, tries valid digits from 1 to 9, and continues recursively. If it reaches a dead end, it returns to an earlier choice and tries another digit.

Conclusion #

Modeling Sudoku with algebraic geometry offers a different and mathematically rich perspective. Polynomials, ideals, and Gröbner bases reveal the structure behind the puzzle. In computational efficiency, however, the theoretical method falls behind standard algorithms such as backtracking. It is still fascinating to see the abstract mathematics hidden inside a simple logic puzzle.