This is the thirtieth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hello! Today we are going to solve Sudoku using ILP.

Description

In Sudoku we need to fill grid with numbers. In every column, in every row, and in nine smaller subgrids we can use every number from to exactly once. We usually start with few fields filled and we need to find the rest. See the picture below (from wikipedia):

In this post we will use basic set operations a lot so make sure that you understand them.

Variables

Let’s start with variables for the problem. We usually use binary variables to indicate decision, however, this time we will use integer variables in range to represent the solutions. It is quite intuitive: after solving the problem we obtain the result by checking the value of variable for given board field. So we define the following variables:

We also make sure that they are in the correct range:

Let’s now define constraints.

Constraints

This part is very easy. We already know how to define “all different” constraint, so all we need to do is to add constraints for every row, every column, and every subgrid:

Code

var board = new int[][]{
	new int []{5,3,0,0,7,0,0,0,0},
	new int []{6,0,0,1,9,5,0,0,0},
	new int []{0,9,8,0,0,0,0,6,0},
	new int []{8,0,0,0,6,0,0,0,3},
	new int []{4,0,0,8,0,3,0,0,1},
	new int []{7,0,0,0,2,0,0,0,6},
	new int []{0,6,0,0,0,0,2,8,0},
	new int []{0,0,0,4,1,9,0,0,5},
	new int []{0,0,0,0,8,0,0,7,9}
};

var width = board[0].Length;
var height = board.Length;

var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
	IntegerWidth = 15,
	Epsilon = 0.1,
	StoreDebugExpressions = false,
	CacheConstants = false,
	StoreDebugConstraints = false
});

Console.WriteLine("Create variables");
var fields = Enumerable.Range(0, height).Select(r => Enumerable.Range(0, width).Select(c => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray()).ToArray();

Console.WriteLine("Set ranges");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		solver.Set<LessOrEqual>(fields[row][column], solver.FromConstant(9));
		solver.Set<GreaterOrEqual>(fields[row][column], solver.FromConstant(1));
	}
}

Console.WriteLine("Set known");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		if(board[row][column] != 0)solver.Set<Equal>(fields[row][column], solver.FromConstant(board[row][column]));
	}
}

Console.WriteLine("Rows");
for(int row = 0; row < height;++row){
	solver.Set<AllDifferent>(fields[row][0], fields[row].Skip(1).ToArray());
}

Console.WriteLine("Columns");
for(int column = 0; column < width; ++ column){
	solver.Set<AllDifferent>(fields[0][column], Enumerable.Range(1, height-1).Select(row => fields[row][column]).ToArray());
}

Console.WriteLine("Quadrants");
for(int row = 0; row < height / 3;++row){
	for(int column = 0; column < width / 3; ++ column){
		var quandrant = Enumerable.Range(0, 3).SelectMany(i => Enumerable.Range(0, 3).Select(j => fields[row * 3 + i][column * 3 + j])).ToArray();
		solver.Set<AllDifferent>(quandrant[0], quandrant.Skip(1).ToArray());
	}
}

solver.AddGoal("goal", solver.FromConstant(0));
solver.Solve();

for(int row = 0; row < height;++row){
	if(row % 3 == 0)Console.WriteLine("-------------");
	for(int column = 0; column < width; ++ column){
		if(column % 3 == 0)Console.Write("|");
		Console.Write(solver.GetValue(fields[row][column]));
	}
	Console.Write("|");
	Console.WriteLine();
}
Console.WriteLine("-------------");

Output:

Tried aggregator 1 time.
MIP Presolve eliminated 7995 rows and 3969 columns.
MIP Presolve modified 23909 coefficients.
All rows and columns eliminated.
Presolve time = 0.02 sec. (10.42 ticks)

Root node processing (before b&c):
  Real time             =    0.02 sec. (10.97 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.02 sec. (10.97 ticks)
-------------
|534|678|912|
|672|195|348|
|198|342|567|
-------------
|859|761|423|
|426|853|791|
|713|924|856|
-------------
|961|537|284|
|287|419|635|
|345|286|179|
-------------

Summary

As we can see, our toolkit for building ILP formulas is quite powerfull and we are able to solve Sudoku almost instantly just by translating rules of the game (nine different numbers in each column, nine different numbers in each row, nine different numbers in each subgrid) to mathematical operators.

This is the twenty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hello! Today we are going to solve nonograms using ILP.

Task description

Nonograms are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. Images are usually black and white, however, they can be colored. Below is an example of a nonogram (by wikipedia):

We will solve black and white nonogram, so we assume that numbers describe blocks of black fields whit at least one white field between every block.

Variables

As with most of the riddles we start with defining binary variables representing decisions. Let’s assume that the picture has size (width and height). For every field we define a binary variable meaning whether we fill this field or no:

We also need to define variables representing top-left blocks’ corners. Let’s introduce the following notation: means number of blocks in -th column, means length of -th block in -th column. Analogously, means number of block in -th row, means length of -th block in -th row. We define the following binary variables:

Variable means whether -th block in -th column starts (e.g., its top-left field is) in field . Analogously, means whether -th block in -th row starts in field .

After solving the problem we obtain the solution from variables . Other variables are used only to specify constraints.

Constraints

We start with two obvious constraints: number of selected fields in each row and each column must match the blocks’ lengths:

Now we need to make sure that in every field there starts at most one block:

Next, we need to make sure that if the block starts in particular field, all fields of this block are selected:

When a particular column block starts in field (which means that is true) then all fields must be true so we use conjunction. The same idea goes for row blocks. We also need to make sure that block does not start close to the boundary:

Finally, we need to take care of blocks ordering. We need to make sure that block occur in proper order. We use the following idea: if some column block starts in field which means that is true, previous block must start in some field where . So the sum of variables indicating start of the block must be true. The following constraints take care of this:

If is true then sum of must be true in order to fulfill the constraint. On the other hand, if is false, then sum of can have any value. The same goes for rows.

Summary

As we can see implementation is rather easy. The most difficult part is related to ordering the blocks, the rest is pretty straightforward. Next time we will solve sudoku.

This is the twenty seventh part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi! Today we are going to solve Einstein’s five houses riddle using ILP!

Introduction

In the riddle we have five houses. Person living in every house can be described using five traits (nationality, favorite drink, spoked stuff, color of the house, and favorite pet). For every trait we have five different values: there are five colors, five animals, five drinks etc. We are given some logical constraints describing the persons and wee need to find the final matching between houses and traits. Looks like ideal case for our ILP program!

Matrix of traits

We have the following traits:

We define the following binary variables:

Every variable answers the question if the associated house has the associated trait set to true. For instance, set to true means that the house number is blue, whereas would mean that the guy living in house number smokes Kools.

Constraints

We need to add basic constraints that one trait is associated with exactly one house:

Now we can add formulas for constraints specified in the riddle.

The Englishman lives in the red house.

The Spaniard owns the dog.

Coffee is drunk in the green house.

The Ukrainian drinks tea.

The green house is immediately to the right of the ivory house.

The Old Gold smoker owns snails.

Kools are smoked in the yellow house.

Milk is drunk in the middle house.

The Norwegian lives in the first house.

The man who smokes Chesterfields lives in the house next to the man with the fox.

Kools are smoked in the house next to the house where the horse is kept.

The Lucky Strike smoker drinks orange juice.

The Japanese smokes Parliaments.

The Norwegian lives next to the blue house.

Summary

As we can see it is very easy to solve the Einstein’s riddle using ILP. Most of the constraints are straightforward, only constraints of type “something is in the house next to” are a bit more difficult.

This is the seventeenth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi all. Today we are going to solve another riddle, called Lonpos 505 Puzzle. It is very similar to the riddle from the previous part so you might want to read it first.

Game

In the game we are given a set of 12 elements with different shapes:

We are also give a starting position of elements:

Our goal is to add missing elements in a way that the board is filled completely:

Let’s begin.

Variables

Our board has 55 fields, we have 12 elements. For every field position and for every element we need variables representing placement of the element on the board, so we have the following binary variables:

Just like in the previous part, variable being equal to one means that the following field is occupied by the element.

Shapes

Since every element has different shape, we will need a different set of constraints for different elements. For instance, element A has four pieces and can be placed in one out of eight positions (4 rotations on a plane and two rotations of the sides, see the pciture), whereas element K can be placed in exactly one way.

So we do the following:
For every position , for every element , and for every rotation of this element we need to choose variables representing placement of this element on the plane. For instance: let’s say that we want to place second rotation of element A in the position . We would need to consider the following variables:

Next, we calculate conjunction of these variables. If it is true it means that all these fields are occupied by element one. This means:

means element , rotation , position .
We calculate these variables for every rotation of every element placed on every possible position on the board.

Exactly one rotation of an element

Since we have multiple rotations for almost every element, we need to make sure that at most one rotation for given position is selected:

What’s more, we need to select exactly one placement of an element, which means that we need to select exactly one rotation for particular element:

Exactly one element in a position

If we would try to solve the problem right now, we would end up with exactly one rotation of all elements placed on the board, however, these elements would probably land all in the same place. We need to make sure that for every position there is exactly one piece of elements there:

Starting position

If we want to solve the riddle for a given starting position, all we need to do is set subset of variables to one, as described in instruction.

Summary

As we can see, the implementation looks a bit simpler than in previous part. However, this problem is much more difficult than previous one because we have many more variables and much more difficult constraints. During my tests I was able to solve the problem easily when 8 elements were already placed on the board, however, I didn’t get any solution in an hour for a problem with only 4 elements placed on the board as a starting position. You can verify for yourself that this problem is not as easy as it looks like.

Bonus chatter: Lonpos 500 Puzzle is very interesting game. It also has version in 3D space — try to implement it using ILP.

This is the sixteenth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi all. Today we are going to use ILP to solve a cube riddle. This will be a basic application of ILP approach because we are not going to define any meaningful cost function. All we want to get is any solution fulfilling provided constraints. Let’s go.

Problem description

We have the following cube:


We have nine l-shape elements which we can use to build a bigger cube with a side of length three. Elements are identical, we can rotate them but we cannot change their shape.

This problem was posted as a question on 4programmers forum

For this problem we will utilize a so called zero-one linear programming. It is a special case of ILP with binary variables only. This approach is often used to solve decision problems for which we want to get any solution, disregarding the cost function.

Necessary variables

We start with defining necessary variables. We have nine elements, every element consists of three “pieces”. For each element we define a binary variables saying whether this element has piece in a specific cube position. So we end up with:

where is a number of element (so it is from to ) and are coordinates of the cube. So we have binary variables. Every variable is allowed to be zero or one. Zero means that the particular element has no piece in the specific coordinates.
Having these variables let’s start with adding constraints.

Three pieces for every element

We start with an obvious constraint. Every element should have exactly three pieces. This means the following:

We sum for indexes which make sense. For every element we want the sum of variables for every coordinate for this element to be equal to three.

Stop tearing elements

If we would solve the problem right now, we would end up with elements scattered throughout the cube. Elements would probably be tore apart, however, all of them would have exactly three pieces.
In order to avoid tearing element apart, we need to make sure that its pieces are next to each other. We say that two pieces are one next to another when they are neighbours in one of three possible directions (along axis, along axis, along axis). We get the following constraint:

This formula means that for every piece and for every position we check whether position and any of its neighbouring positions are occupied by pieces of one element. If it is so, these variables will be equal to , so by multiplying them we will get . Since we deal with binary variables only, we can use just a conjunction defined in part 1.

Bending elements

If we would solve the problem right now, elements would have exactly three pieces, and pieces would be next to each other. However, we might end up with a straightened element, e.g., element with all pieces along one axis.
In order to avoid this, we need to add the following constraints:

Let’s take the first one constraint. For every element and for every position on the bottom side of the cube we sum all elements along the axis. So we sum take all positions for one vertical line, sum their variables and make sure that there are at most two pieces on that line. Next two constraints do the same for axis and axis respectively.

Exactly one piece in one place

Once again, if we would solve the problem right now, we would end up with elements with correct shape (e.g., with three pieces and in l-shape), however, all this elements still might be in exactly the same place. In order to avoid that, we need to make sure that for every coordinate there is exactly one piece of exactly one element:

For every position we sum variables for all elements and we require that this sum is equal to exactly one. This means that exactly one variable will be true.

Summary

As we can see, this riddle can be solved really straightforward. We start with required variables and add constraints to make our elements look more realistic. Finally, we put elements in places and build the actual cube.
I checked this naive implementation using CPLEX and the solver was able to find the solution in less than 200 miliseconds. Not bad.
Next time we are going to solve similar problem, however, we will need to deal with elements of different shapes. Stay tuned.