Design your model

Let’s (make qaekwy) solve any Sudoku

Welcome to this step-by-step quick-start tutorial on harnessing the power of Qaekwy for constraint programming. In this tutorial, you will swiftly learn how to create a simple Sudoku solver using Qaekwy.

By following this tutorial, you’ll grasp the fundamental concepts of defining variables, constraints, and experience the seamless interaction with Qaekwy’s solver engine.

Let’s dive in and unravel the world of constraint programming by creating an efficient Sudoku solver from scratch !

Define the grid

Let’s first create the SudokuGrid class that inherits from the IntegerVariableArray class and is designed to create a Sudoku grid instance.

A Sudoku grid instance is a 9x9 array variable containing values between 1 and 9.

from qaekwy.model.variable.integer import IntegerVariableArray

class SudokuGrid(IntegerVariableArray):
    def __init__(self, grid_value=None):
        super().__init__(
            var_name="grid",  # Variable name in the Qaekwy model
            length=9*9,       # 9x9 array variable
            domain_low=1,     # Minimum value: 1
            domain_high=9     # Maximum value: 9
        )


        # This variable contains the 9x9 array's initial values.
        # This variables is not part of the Qaekwy model itself
        # but will be used after to enforce the initial values
        # to remain the same, thanks to the constraints that will
        # be defined.
        self.grid_value = grid_value

Define the problem

Next, we’ll model the Sudoku puzzle-solving problem using the Qaekwy Modeller class. This class is responsible for adding constraints that ensure the rules of Sudoku are followed and the initial given values are satisfied.

The Sudoku problem has 3 types of contraints:

  • The 3x3 distinct values for the 9 blocks
  • The Row distinct values for the 9 rows
  • The Col distinct values for the 9 columns

To enforce these rules in our modelling, we will need 3 constraints from Qaekwy:

  • ConstraintDistinctSlice
  • ConstraintDistinctRow
  • ConstraintDistinctCol

In order to fully model the problem, we need to take into account the initial values of the Sudoku grid. To do this, we’re going to require a fourth constraint to ensure that the initial values are preserved:

  • RelationalExpression

The RelationalExpression is used to enfore a relational expression as a constraint over our grid’s initial values. In our case, any value different from 0 is identified as constant.

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

        # Add constraints for distinct values within 3x3 slices
        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,
                    )
                )

        # Add constraints for distinct values within rows and columns
        for i in range(0, 9):

            # Rows
            self.add_constraint(
                constraint=ConstraintDistinctRow(
                    var_1=self.grid,
                    size=9,
                    idx=i
                )
            )

            # Columns
            self.add_constraint(
                constraint=ConstraintDistinctCol(
                    var_1=self.grid,
                    size=9,
                    idx=i
                )
            )

        # Add constraints for initial given values. Here,
        # any value different from 0 is identified as constant
        # and is put under constraint.
        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]
                    )
                )

Add the grid to the model

After modelling the constraints, let’s add the grid variable to the model. We can append the following instruction to the previous block of code:

        # Add the Sudoku grid as a variable to the problem
        self.add_variable(self.grid)

Define the searcher

Qaekwy requires to specify a searcher. A searcher is a methodology used to explore the solution tree. In this example, the Depth-First Search is perfectly acceptable.

Let’s append the searcher setting to our previous block of code:

        # Set the search strategy to Depth-First Search (DFS)
        self.set_searcher(SearcherType.DFS)

What’s next ?

You now have a complete generic definition of the Sudoku problem through the constraints defined in your SudokuProblem class and your generic grid defined by SudokuGrid.

The next steps are:

  • Submit a Sudoku grid
  • Call the solver
  • Print the solution