Sudoku is a classic puzzle game that challenges your logical thinking and problem-solving skills. Solving Sudoku puzzles algorithmically can be an interesting application of linear programming, and in this blog, we will demonstrate how to solve Sudoku puzzles using Python and the PuLP library.

Problem Description

A Sudoku puzzle is a 9x9 grid that must be filled with numbers from 1 to 9. The puzzle is divided into 9 smaller 3x3 grids called boxes, and each row and column must contain unique numbers from 1 to 9. The objective is to fill in the entire grid according to these rules. Sudoku puzzles often come with some pre-filled numbers as clues.

Formulation

Identify the Decision Variables

To formulate the Sudoku problem as a linear program, we create 729 binary variables (0–1), representing 9 variables for each of the 81 squares. Each of these variables corresponds to a number that might be in that square. The binary nature of the variable indicates whether a number is present (1) or not (0) in that square. Since only one number can be placed in a square, exactly one of the 9 variables for each square must be true (1), and the others must be false (0).

Formulate the Objective Function

In Sudoku, there is no concept of optimizing for a better solution. Our goal is to find a solution that satisfies all constraints. Therefore, we do not define an objective function with PuLP.

Formulate the Constraints

1. Each row must contain all numbers from 1 to 9.
2. Each column must contain all numbers from 1 to 9.
3. Each box (3x3 grid) must contain all numbers from 1 to 9.
4. Each square must have exactly one number (binary constraint).
5. The starting Sudoku numbers (clues) must remain fixed in the solution.

Code

Let's implement the solution using PuLP: Full Colab Notebook Here

# Import PuLP modeler functions
from pulp import *

# Create Sudoku Input (Number in Grid, Row, Column)
input_data = [
    (5, 1, 1),
    (6, 2, 1),
    (8, 4, 1),
    (4, 5, 1),
    (7, 6, 1),
    (3, 1, 2),
    (9, 3, 2),
    (6, 7, 2),
    (8, 3, 3),
    (1, 2, 4),
    (8, 5, 4),
    (4, 8, 4),
    (7, 1, 5),
    (9, 2, 5),
    (6, 4, 5),
    (2, 6, 5),
    (1, 8, 5),
    (8, 9, 5),
    (5, 2, 6),
    (3, 5, 6),
    (9, 8, 6),
    (2, 7, 7),
    (6, 3, 8),
    (8, 7, 8),
    (7, 9, 8),
    (3, 4, 9),
    (1, 5, 9),
    (6, 6, 9),
    (5, 8, 9),
]

# Define the values, rows, and columns
VALS = ROWS = COLS = range(1, 10)

# Create a list of boxes
Boxes = [
    [(3 * i + k + 1, 3 * j + l + 1) for k in range(3) for l in range(3)]
    for i in range(3)
    for j in range(3)
]

# Create the problem
prob = LpProblem("Sudoku Problem")

# Create the decision variables
choices = LpVariable.dicts("Choice", (VALS, ROWS, COLS), cat="Binary")

# Constraint: Only one value can be in each square
for r in ROWS:
    for c in COLS:
        prob += lpSum([choices[v][r][c] for v in VALS]) == 1

# Constraint: Each number (value) can only occur once in each row, column, and box
for v in VALS:
    for r in ROWS:
        prob += lpSum([choices[v][r][c] for c in COLS]) == 1
    for c in COLS:
        prob += lpSum([choices[v][r][c] for r in ROWS]) == 1
    for b in Boxes:
        prob += lpSum([choices[v][r][c] for (r, c) in b]) == 1


for v, r, c in input_data:
    prob += choices[v][r][c] == 1

# Write the problem to an LP file
prob.writeLP("Sudoku.lp")

# Solve the problem
prob.solve()

# Check the status of the solution
print("Status:", LpStatus[prob.status])

# Write the solution to a text file
sudokuout = open("sudokuout.txt", "w")
for r in ROWS:
    if r in [1, 4, 7]:
        sudokuout.write("+-------+-------+-------+\n")
    for c in COLS:
        for v in VALS:
            if value(choices[v][r][c]) == 1:
                if c in [1, 4, 7]:
                    sudokuout.write("| ")
                sudokuout.write(str(v) + " ")
                if c == 9:
                    sudokuout.write("|\n")
sudokuout.write("+-------+-------+-------+")
sudokuout.close()

# Print the location of the solution
print("Solution Written to sudokuout.txt")

with open('/content/sudokuout.txt', 'r') as file:
  for line in file:
      print(line, end='')

• Parts of this article were written using Generative AI
• Subscribe/leave a comment if you want to stay up-to-date with the latest AI trends.

Plug: Checkout all my digital products on Gumroad here. Please purchase ONLY if you have the means to do so. Use code: MEDSUB to get a 10% discount!