Simple sudoku solver using logical constraints (with GUI)

Description: Simple sudoku model with two formulations: as a Constraint Programming problem using the alldiff operator and as a MIP. Note that the CP formulation is more natural but it needs a solver supporting logical constraints or a MIP solver with automatic reformulation support (see here for more information). The two formulations will be differentiated using AMPL’s handy named problem concept. A simple GUI implemented using ipywidgets helps with data visualization and specification.

Tags: amplpy, constraint-programming, GUI, highlights

Notebook author: Christian Valente <christian.valente@gmail.com>

Model author: Christian Valente

# Install dependencies (using ipywidgets for the simple GUI)
%pip install -q amplpy ipywidgets

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["highs"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Define the AMPL model of a sudoku game.

In this example, we will show two models to solve a sudoku.

1. MIP formulation where we will use a binary variable to indicate if a cell is occupied with any of the possible numbers.

2. Constraint Programming formulation using the logical operator alldiff to avoid the explicit use of binary variables.

That the model is parametric in terms of size: BASE defines the size of the (square) subgrids making up the game. For a normal sudoku game, where the numbers go from 1 to 9, this has to be set to 3.

Common infrastructure

The entities defined in the next cell are shared by both the MIP and the CP formulations

%%ampl_eval
reset;
option solver highs;
# The base number of this sudoku; 3 is the default (9 numbers game)
param BASE default 3;
# The line/column lenght, derived from BASE
param L := BASE*BASE;

# Set of all Rows
set ROWS := {1..L};
# Set of all columns
set COLS := {1..L};
# This indexed set memorizes the tuples of coordinates for each 
# sub-square making up the grid
set SUBSQUARES{sr in 1..BASE, sc in 1..BASE} within {ROWS, COLS}
	            = {(sr-1)*BASE+1..sr*BASE, (sc-1)*BASE+1..sc*BASE};

# The variables representing the numbers at all positions
var x{ROWS, COLS} >=1, <=L integer;

# Set this parameter to non-zero to force a position to have
# that value
param givenData{ROWS, COLS} default 0;

# Dummy objective, just to "encourage" the solver to get the same
# objective function in case of a degenerate sudoku
maximize z: x[1,1];

subject to
# Fix input data (forces the variable at the corresponding location to have
# the same value as the parameter)
fixGivenData{r in ROWS, c in COLS : givenData[r,c] > 0}: x[r,c] = givenData[r,c];

MIP formulation

In the MIP formulation, we will use the binary variable IsN, defined for all the cells and all the possible numbers, to indicate if a specific number is present in the related cell. A set of constraints will then be needed to ensure that:

1. MIPOnlyOneNumber each cell contains only one number

2. MIPEachRowOneNumber each row contains all the possible numbers

3. MIPEachColOneNumber each column contains all the possible numbers

4. MIPEachSquareOneNumber each sub-grid contains all the possible numbers

5. MIPLinkToX the variable IsN is linked to the variable x above. Note that this is not strictly necessary for the model itself, but it is useful when sharing the same base entities with the CP model.

%%ampl_eval
# Definition of MIP model
var IsN{1..L, COLS, ROWS} binary;

# Each position only one number
MIPOnlyOneNumber{r in ROWS, c in COLS}: sum{n in 1..L} IsN[n,c,r] = 1;
# Each number must be present in each row once
MIPEachRowOneNumber{r in ROWS, n in 1..L}: sum{c in COLS} IsN[n,c,r] = 1;
# Each number must be present in each col once
MIPEachColOneNumber{r in COLS, n in 1..L}: sum{c in ROWS} IsN[n,c,r] = 1;
# Each number must be present in each subsquare once
MIPEachSquareOneNumber{n in 1..L, sr in 1..BASE, sc in 1..BASE}: 
	sum{(r, c) in SUBSQUARES[sr, sc]} IsN[n, c, r] = 1;
# Link to the logical model variable
MIPLinkToX{r in ROWS, c in COLS}: sum{n in 1..L} IsN[n,c,r]*n =x[r,c];
# Define a named problem to quickly switch between formulations
problem sudokuMIP: x, IsN, z, fixGivenData, MIPOnlyOneNumber, MIPEachRowOneNumber, MIPEachColOneNumber, MIPEachSquareOneNumber, MIPLinkToX;

CP formulation

The Constraint Programming formulation is much more readable and compact, and it follows the human intuitive understanding of the game. Using the operator alldiff, which forces all variables passed as operands to assume different values, we simply need the following constraints:

1. rowsAllDiff each x in a row must contain a different number

2. colsAllDiff each x in a column must contain a different number

3. squaresAllDiff each x in a subsquare must contain a different number

%%ampl_eval
# Definition of logical constrained model
# All numbers in one row have to be different
rowsAllDiff{r in ROWS}:   alldiff{c in COLS} x[r,c];
# All numbers in one column have to be different
colsAllDiff{c in COLS}:   alldiff{r in ROWS} x[r,c];
# All numbers for each subsquare must be different
squaresAllDiff{sr in 1..BASE, sc in 1..BASE}: alldiff{(c,r) in SUBSQUARES[sr,sc]} x[r,c];
# Define a named problem to quickly switch between formulations
problem sudokuCP: x, z, fixGivenData, rowsAllDiff, colsAllDiff, squaresAllDiff;

Data definition

This is an example used to populate the sudoku below. It has the standard size (9x9), so we specify a BASE of 3; please note that since the parameter had a default of 3, this step wasn’t needed.

from random import seed, random

BASE = 3
seed(1234)


def random_state():
    ampl.param["BASE"] = BASE
    ampl.param["givenData"] = {(1, 1): 0}
    if BASE != 3:
        return
    solution = [
        [2, 5, 7, 8, 6, 3, 1, 4, 9],
        [4, 9, 6, 5, 7, 1, 8, 3, 2],
        [8, 1, 3, 9, 4, 2, 7, 6, 5],
        [1, 6, 5, 2, 9, 4, 3, 7, 8],
        [9, 8, 4, 1, 3, 7, 5, 2, 6],
        [3, 7, 2, 6, 5, 8, 4, 9, 1],
        [7, 2, 9, 4, 8, 5, 6, 1, 3],
        [5, 3, 1, 7, 2, 6, 9, 8, 4],
        [6, 4, 8, 3, 1, 9, 2, 5, 7],
    ]
    ampl.param["givenData"] = {
        (i + 1, j + 1): solution[i][j] if random() <= 1 / 3.0 else 0
        for i in range(9)
        for j in range(9)
    }


random_state()

GUI-related code

The following code creates the Class SudokuSchema, a convenient wrapper around ipywidgets to create and display a grid that resembles the game board. It provides functions to get and set the values in the schema itself.

import ipywidgets as widgets
from IPython.display import display


class SudokuSchema:
    def _create_one_grid(self, startRow: int, startCol: int):
        gridItems = [
            widgets.VBox(
                [self.items[row, col] for row in range(startRow, startRow + self.BASE)]
            )
            for col in range(startCol, startCol + self.BASE)
        ]
        return widgets.HBox(
            gridItems, layout=widgets.Layout(border="solid 2px", width="140px")
        )

    def __init__(self, base):
        """Initializes a sudoku schema with base dimension BASE"""
        self.BASE = base
        self.BSQUARED = base**2
        # Create all widgets
        self.items = {
            (r, c): widgets.BoundedIntText(
                value=0,
                min=0,
                max=self.BASE**4,
                step=1,
                description="",
                layout=widgets.Layout(width="40px", height="40px"),
            )
            for r in range(self.BSQUARED)
            for c in range(self.BSQUARED)
        }
        self.sudoku = widgets.HBox(
            [
                widgets.VBox(
                    [
                        self._create_one_grid(r, c)
                        for r in range(0, self.BSQUARED, self.BASE)
                    ]
                )
                for c in range(0, self.BSQUARED, self.BASE)
            ]
        )
        self.create_selection_button()
        self.create_buttons()

    def display(self):
        """Display the current schema on the notebook"""
        display(self.sudoku)
        display(self.selector)
        if BASE == 3:
            display(widgets.HBox([self.random_button, self.solve_button]))
        else:
            display(widgets.HBox([self.solve_button]))

    def get_values(self):
        """Get the current non zero values as a (r,c) : value dictionary"""
        return {
            (r + 1, c + 1): self.items[r, c].value
            for r in range(self.BSQUARED)
            for c in range(self.BSQUARED)
            if self.items[r, c].value != 0
        }

    def set_values(self, values: dict):
        """Set the values in the schema from the specified (r,c) : value dictionary"""
        for (r, c), v in values.items():
            self.items[r - 1, c - 1].value = round(v)

    def create_selection_button(self):
        self.selector = widgets.RadioButtons(
            options=["Constraint Programming", "MIP"],
            value="Constraint Programming",
            layout={"width": "max-content"},
            description="Formulation:",
            disabled=False,
        )

    def get_selected_formulation(self):
        return self.selector.value

    def set_random_board(self):
        random_state()
        self.set_values(ampl.get_data("givenData").to_dict())

    def create_buttons(self):
        self.random_button = widgets.Button(
            description="Random board",
            disabled=False,
            button_style="info",
            tooltip="Random board",
            icon="bolt",
        )
        self.random_button.on_click(lambda btn: self.set_random_board())
        self.solve_button = widgets.Button(
            description="Solve",
            disabled=False,
            button_style="success",
            tooltip="Solve model",
            icon="bolt",
        )
        self.solve_button.on_click(solve_and_display)

Solve and display

Pressing the Solve model button below the schema the sudoku will be solver by means of the function below. At first, we get which formulation is selected, translate it into the appopriate problem name, then use the AMPL statemnent solve problemname; to solve the instance.

# Solve and display the solution
def solve_and_display(button):
    # Get the selected formulation from the radio button
    formulation = sudoku.get_selected_formulation()
    if formulation == "Constraint Programming":
        problem_name = "sudokuCP"
    else:
        problem_name = "sudokuMIP"

    print(f"Solving the {formulation} formulation!")
    # Solve the selected model
    ampl.eval(f"solve {problem_name};")

    # Get the data from AMPL and assign them to the entities making up the grid above
    sudoku.set_values(ampl.get_data("x").to_dict())

Show the sudoku schema

The following cell creates the sudoku schema - of the size specified in BASE and visualizes it. It also shows a radio button that allows you to choose between the two formulations and a button to begin the solution process. The button will call the function Solve_and_display defined above.

# Create and display the grid
sudoku = SudokuSchema(BASE)
sudoku.display()
# Display existing values
sudoku.set_values(ampl.get_data("givenData").to_dict())

Solving the Constraint Programming formulation!
HiGHS 1.4.0: HiGHS 1.4.0: optimal solution; objective 6
0 simplex iterations
1 branching nodes

previous

Roll Cutting - Revision 1 & 2

next

Solution check: discontinuous objective function