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:

from qaekwy.model.modeller import Modeller
from qaekwy.model.searcher import SearcherType
from qaekwy.model.variable.integer import IntegerVariableArray
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.constraint.distinct import (
    ConstraintDistinctCol,
    ConstraintDistinctRow,
    ConstraintDistinctSlice,
)
from qaekwy.engine import DirectEngine


class SudokuGrid(IntegerVariableArray):
    def __init__(self, grid_value=None):
        super().__init__(
            var_name="grid",  # Identifier for the variable array within the model.
            length=9*9,       # Total number of elements in the array (9*9).
            domain_low=1,     # Defines the lower bound of the variable domain.
            domain_high=9     # Defines the upper bound of the variable domain.
        )

        # This attribute holds the initial state of the grid.
        # It is not a component of the solver's model but is used
        # to establish constraints for the puzzle's given values.
        self.grid_value = grid_value

class SudokuProblem(Modeller):
    def __init__(self, grid: SudokuGrid):
        super().__init__()
        self.grid = grid

        # Impose distinct value constraints on all 3x3 subgrids.
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                self.add_constraint(
                    constraint=ConstraintDistinctSlice(
                        var_1=self.grid,
                        size=9,
                        offset_start_x=i,
                        offset_end_x=i + 3,
                        offset_start_y=j,
                        offset_end_y=j + 3,
                    )
                )

        # Impose distinct value constraints on all rows and columns.
        for i in range(0, 9):
            self.add_constraint(
                constraint=ConstraintDistinctRow(
                    var_1=self.grid,
                    size=9,
                    idx=i
                )
            )
            self.add_constraint(
                constraint=ConstraintDistinctCol(
                    var_1=self.grid,
                    size=9,
                    idx=i
                )
            )

        # Impose equality constraints for the initial non-zero values of the grid.
        # Any value other than 0 is treated as a constant.
        for i in range(0, 81):
            if self.grid.grid_value[i] != 0:
                self.add_constraint(
                    constraint=RelationalExpression(
                        self.grid[i] == self.grid.grid_value[i]
                    )
                )

2. Solving the Puzzle

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

# Instantiate the SudokuGrid with a specific puzzle configuration.
# Values of 0 represent variables to be solved.
my_grid = SudokuGrid(
    grid_value=[
        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
    ]
)

# Create the problem instance
sudoku_problem = SudokuProblem(my_grid)

# Create an engine and solve the model
engine = DirectEngine()

# Submit the problem model to the Qaekwy engine for resolution.
response = qaekwy_engine.model(model=sudoku_problem)

# Extract the list of solutions from the engine's response.
list_of_solutions = response.get_solutions()

# Iterate through and display the solution(s).
for solution_item in list_of_solutions:
    for c in range(0, 81, 9):
        print(solution_item.grid[c:c+9])

Expected Output

[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]