Design your model

Introduction to Sudoku Problem Modeling

This chapter demonstrates how to design a constraint satisfaction model. As a concrete example, we model the classic Sudoku puzzle, showing how variables and constraints are declared directly through the Model interface.

Grid Representation as an Integer Matrix

A Sudoku grid consists of 9×9 cells, each containing an integer between 1 and 9. In Qaekwy, this structure is naturally represented using an integer matrix.

import qaekwy as qw

# Initialize the model container
m = qw.Model()

# Create a 9x9 matrix of integer variables
# Each variable can take a value between 1 and 9 (inclusive)
grid = m.integer_matrix("grid", rows=9, cols=9, domain=(1, 9))

Constraint Formulation

The rules of Sudoku are translated into formal constraints. The Model instance m acts as the central registry for these rules. We can retrieve specific sections of our variables using the helper methods .row(), .col(), and .slice() provided by the matrix object.

The Sudoku puzzle is governed by three primary uniqueness rules:

Row and Column Constraints

Each of the nine rows and nine columns must contain distinct values. We iterate through the range of 0 to 8, retrieving the variable list for each row and column, and apply m.constraint_distinct.

for i in range(9):
    # Ensure all variables in row 'i' are unique
    m.constraint_distinct(grid.row(i))
    
    # Ensure all variables in column 'i' are unique
    m.constraint_distinct(grid.col(i))

Block (Subgrid) Constraints

Each of the nine 3x3 subgrids (blocks) must contain distinct values. We use the .slice() method to extract these 3x3 regions. The slice method accepts (start_row, start_col, end_row, end_col) coordinates.

# Iterate in steps of 3 (0, 3, 6) to find the top-left corner of each block
for i in range(0, 9, 3):
    for j in range(0, 9, 3):
        # Extract the 3x3 block and enforce uniqueness
        m.constraint_distinct(grid.slice(i, j, i + 3, j + 3))

Initial State Constraints

Finally, we must respect the initial state of the puzzle (the “clues”). We iterate through our Python input data (e.g., a list of lists). If a value is non-zero, we constrain the corresponding variable in our Qaekwy grid to equal that specific value.

Note that Qaekwy supports standard Python comparison operators (like ==) inside m.constraint().

# Initial Sudoku grid, with 0 for empty cells Qaekwy will have to assign
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]
]


for i in range(9):
    for j in range(9):
        # If the cell is not empty (0 represents empty in our data)
        if my_problem[i][j] != 0:
            # Constrain the model variable at [i][j] to equal the input value
            m.constraint(grid[i][j] == my_problem[i][j])