# 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()
```

## 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
```