Design your model

Introduction to Sudoku Problem Modeling

This document serves as a technical guide to modeling constraint satisfaction problems (CSPs) using the Qaekwy library. The classic game of Sudoku is utilized as the case study to demonstrate the fundamental principles of defining variables and formulating constraints within the Qaekwy framework.

The objective is to construct a generic and reusable model that programmatically represents the rules of any Sudoku puzzle. This involves a formal definition of the problem’s variables and the explicit declaration of the logical constraints that govern them.

Grid Representation as a Variable Array

The foundational step in modeling the Sudoku puzzle is the representation of the 9x9 grid. This is achieved by defining a specialized class, SudokuGrid, which inherits from IntegerVariableArray. This class encapsulates the properties of the Sudoku grid, which is fundamentally a one-dimensional array of 81 integer variables, each with a domain restricted to the values {1, …, 9}.

from qaekwy.model.variable.integer import IntegerVariableArray

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

Constraint Formulation

The rules of Sudoku are translated into a set of formal constraints using the Modeller class. This class aggregates all variables and constraints that constitute the problem definition. The Sudoku puzzle is governed by three primary uniqueness constraints:

  1. Block Constraints: Each of the nine 3x3 subgrids (blocks) must contain distinct values.
  2. Row Constraints: Each of the nine rows must contain distinct values.
  3. Column Constraints: Each of the nine columns must contain distinct values.

These rules are implemented using ConstraintDistinctSlice, ConstraintDistinctRow, and ConstraintDistinctCol, respectively. An additional constraint, RelationalExpression, is employed to fix the initial, non-zero values of the puzzle grid, ensuring they remain constant during the solving process.

from qaekwy.model.modeller import Modeller
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.constraint.distinct   import ConstraintDistinctCol
from qaekwy.model.constraint.distinct   import ConstraintDistinctRow
from qaekwy.model.constraint.distinct   import ConstraintDistinctSlice

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

Model Assembly and Search Strategy

With the constraints fully defined, the grid variable array is formally added to the model. Subsequently, a search strategy must be specified to instruct the engine on how to explore the solution space. For this class of problem, a Depth-First Search (DFS) is a conventional and effective choice.

        # Add the Sudoku grid variable array to the problem definition.
        self.add_variable(self.grid)

        # Specify the search methodology.
        self.set_searcher(SearcherType.DFS)

Next Steps

The SudokuProblem and SudokuGrid classes now provide a complete, generic model of a Sudoku puzzle. The subsequent phase involves instantiating this model with a specific puzzle, submitting it to the solver engine, and processing the resultant solution.