๐งฉ 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:
- Distinct Rows: Each row must contain the digits 1 through 9 with no repeats.
- Distinct Columns: Each column must contain the digits 1 through 9 with no repeats.
- Distinct 3x3 Squares: Each 3x3 square must contain the digits 1 through 9 with no repeats.
- 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]