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). 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.
MIP formulation where we will use a binary variable to indicate if a cell is occupied with any of the possible numbers.
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:
MIPUniqueNumberPerPosition
each cell contains only one numberMIPUniqueNumberPerRow
each row contains all the possible numbersMIPUniqueNumberPerColumn
each column contains all the possible numbersMIPUniqueNumberPerSubGrid
each sub-grid contains all the possible numbersMIPLinkToSudokuGrid
the variableNumberPresence
is linked to the variableSudokuGrid
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:
RowAllDifferent
eachSudokuGrid
instance in a row must contain a different numberColumnAllDifferent
eachSudokuGrid
instance in a column must contain a different numberSubGridAllDifferent
eachSudokuGrid
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