Sudoku

Example: Sudoku Solver

In this example, we’ll build a Sudoku solver using Qaekwy. This will show you how to model a problem with array variables and complex constraints.

1. The Model

First, we define the model. The core of the model is a 9x9 grid of integer variables, each with a domain from 1 to 9.

We then add the constraints:

  1. Distinct Rows: Each row must contain the digits 1 through 9 with no repeats.
  2. Distinct Columns: Each column must contain the digits 1 through 9 with no repeats.
  3. Distinct 3x3 Squares: Each 3x3 square must contain the digits 1 through 9 with no repeats.
  4. Initial Values: The initial values of the puzzle must be respected.

Here’s the complete code for the model:

import qaekwy as qw

# Define generic solver
def solve_sudoku(my_problem: list[[int]]) -> None:

    # Instantiate a new model
    m = qw.Model()

    # Define the Matrix
    grid = m.integer_matrix("grid", rows=9, cols=9, domain=(1, 9))

    # Distinct values for each rows and columns
    for i in range(9):
        m.constraint_distinct(grid.row(i))
        m.constraint_distinct(grid.col(i))

    # Distinct values for each 3x3 blocks
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            m.constraint_distinct(grid.slice(i, j,i + 3, j + 3))

    # Setting initial values
    for i in range(9):
        for j in range(9):
            if my_problem[i][j] != 0:
                m.constraint(grid[i][j] == my_problem[i][j])

    # Solve
    s = m.solve_one()

    # Display the result
    s.pretty_print()

2. Solving the Puzzle

Now we can create an instance of our SudokuProblem with a specific puzzle and solve it.

# Instantiate the a grid with a specific puzzle configuration.
# Values of 0 represent variables to be solved.
my_problem = [
    [0, 7, 0,  0, 0, 0,  6, 9, 0],
    [0, 0, 0,  6, 1, 0,  0, 0, 0],
    [0, 9, 2,  0, 0, 0,  0, 5, 0],

    [0, 0, 0,  0, 8, 1,  7, 0, 9],
    [4, 0, 0,  0, 0, 3,  0, 0, 0],
    [0, 0, 0,  0, 5, 6,  1, 0, 8],

    [0, 5, 9,  0, 0, 0,  0, 1, 0],
    [0, 0, 0,  5, 6, 0,  0, 0, 0],
    [0, 2, 0,  0, 0, 0,  5, 7, 0]
]

# Call the model-then-solve-then-print function
solve_sudoku(my_problem)

Expected Output

----------------------------------------
Solution:
----------------------------------------
grid: (9 x 9 matrix)
    1 7 8 3 2 5 6 9 4
    5 4 3 6 1 9 8 2 7
    6 9 2 7 4 8 3 5 1
    2 6 5 4 8 1 7 3 9
    4 8 1 9 7 3 2 6 5
    9 3 7 2 5 6 1 4 8
    7 5 9 8 3 2 4 1 6
    3 1 4 5 6 7 9 8 2
    8 2 6 1 9 4 5 7 3
----------------------------------------