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:
- Block Constraints: Each of the nine 3x3 subgrids (blocks) must contain distinct values.
- Row Constraints: Each of the nine rows must contain distinct values.
- 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.