Simple sudoku solver using logical constraints (with GUI)#

sudoku.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

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). A simple GUI implemented using ipywidgets helps with data visualization and specification.

Tags: amplpy, constraint-programming, GUI, highlights

Notebook author: Christian Valente <ccv@ampl.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: BaseNumber 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

%%writefile common_sudoku.mod
# The base number of this sudoku; 3 is the default (9 numbers game)
param BaseNumber default 3;

# The length of each line/column, derived from BaseNumber
param GridSize := BaseNumber * BaseNumber;

# Set of all Rows
set Rows := {1..GridSize};

# Set of all Columns
set Columns := {1..GridSize};

# This indexed set memorizes the tuples of coordinates for each
# sub-grid making up the sudoku grid
set SubGridCoordinates{SubGridRow in 1..BaseNumber, SubGridCol in 1..BaseNumber}
    within {Rows, Columns}
    = {(SubGridRow-1)*BaseNumber+1..SubGridRow*BaseNumber,
        (SubGridCol-1)*BaseNumber+1..SubGridCol*BaseNumber};

# The variables representing the numbers at all positions in the sudoku grid
var SudokuGrid{Rows, Columns} >= 1, <= GridSize integer;

# Set this parameter to non-zero to fix a position to have that value
param FixedValues{Rows, Columns} default 0;

# Dummy objective, just to "encourage" the solver to have a defined objective
maximize DummyObjective: SudokuGrid[1,1];

# Fix input data (forces the variable at the corresponding location to have
# the same value as the parameter)
subject to FixFixedValues{row in Rows, col in Columns : FixedValues[row, col] > 0}:
    SudokuGrid[row, col] = FixedValues[row, col];
Overwriting common_sudoku.mod

MIP formulation#

In the MIP formulation, we will use the binary variable NumberPresence, 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. MIPUniqueNumberPerPosition each cell contains only one number

  2. MIPUniqueNumberPerRow each row contains all the possible numbers

  3. MIPUniqueNumberPerColumn each column contains all the possible numbers

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

  5. MIPLinkToSudokuGrid the variable NumberPresence is linked to the variable SudokuGrid 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.

%%writefile mip_sudoku.mod
# Binary decision variable that represents the presence or absence of a specific
# number at a particular position in the Sudoku grid.
var NumberPresence{Number in 1..GridSize, Columns, Rows} binary;

# Each position in the grid must have only one number
MIPUniqueNumberPerPosition{row in Rows, col in Columns}:
    sum{num in 1..GridSize} NumberPresence[num, col, row] = 1;

# Each number must appear exactly once in each row
MIPUniqueNumberPerRow{row in Rows, num in 1..GridSize}:
    sum{col in Columns} NumberPresence[num, col, row] = 1;

# Each number must appear exactly once in each column
MIPUniqueNumberPerColumn{col in Columns, num in 1..GridSize}:
    sum{row in Rows} NumberPresence[num, col, row] = 1;

# Each number must appear exactly once in each sub-grid
MIPUniqueNumberPerSubGrid{num in 1..GridSize, SubGridRow in 1..BaseNumber, SubGridCol in 1..BaseNumber}:
    sum{(row, col) in SubGridCoordinates[SubGridRow, SubGridCol]}
    NumberPresence[num, col, row] = 1;

# Link to the SudokuGrid variable
MIPLinkToSudokuGrid{row in Rows, col in Columns}:
    sum{num in 1..GridSize} NumberPresence[num, col, row] * num = SudokuGrid[row, col];
Overwriting mip_sudoku.mod

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. RowAllDifferent each SudokuGrid instance in a row must contain a different number

  2. ColumnAllDifferent each SudokuGrid instance in a column must contain a different number

  3. SubGridAllDifferent each SudokuGrid instance in a subsquare must contain a different number

%%writefile cp_sudoku.mod
# All numbers in one row must be different
subject to RowAllDifferent{row in Rows}:
    alldiff {col in Columns} SudokuGrid[row, col];

# All numbers in one column must be different
subject to ColumnAllDifferent{col in Columns}:
    alldiff {row in Rows} SudokuGrid[row, col];

# All numbers within each sub-grid must be different
subject to SubGridAllDifferent{SubGridRow in 1..BaseNumber, SubGridCol in 1..BaseNumber}:
    alldiff {(row, col) in SubGridCoordinates[SubGridRow, SubGridCol]} SudokuGrid[row, col];
Overwriting cp_sudoku.mod

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.

from random import seed, random

seed(1234)


def random_state(base=3):
    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],
    ]
    return {
        (i + 1, j + 1): solution[i][j] if random() <= 1 / 3.0 else 0
        for i in range(9)
        for j in range(9)
    }

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, and then use the AMPL to solve the instance using the selected formulation.

# Solve and display the solution
def solve_and_display(button):
    # Get the selected formulation from the radio button
    formulation = sudoku.get_selected_formulation()
    ampl = AMPL()
    ampl.read("common_sudoku.mod")
    ampl.param["FixedValues"] = sudoku.get_values()
    if formulation == "Constraint Programming":
        ampl.read("cp_sudoku.mod")
    else:
        ampl.read("mip_sudoku.mod")

    print(f"Solving the {formulation} formulation!")
    # Solve the selected model
    ampl.solve(solver="highs")

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

Show the sudoku schema#

The following cell creates the sudoku schema - of the size specified 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=3)
sudoku.display()
Solving the Constraint Programming formulation!
HiGHS 1.7.1: HiGHS 1.7.1: optimal solution; objective 6
123 simplex iterations
1 branching nodes