An instance of size 5 for the TSP problem
Say we want to print simple additions for each (a, b) such that 1 <= a <= b <= 10.
The C++ way is pretty straightforward, for such an easy task :
{
for (int a = 1 ; a <= 10 ; ++a)
for (int b = a ; b <= 10 ; ++b)
cout << a << " + " << b << " = " << a+b << endl;
}
When doing Constraint Programming though, we don't want to iterate over the values of each variable. We don't want either to compute anything ourselves !
All that we want is to declare some variables, put some constraints over them, and finally just obtain the solutions and use them.
Using EasyCP to do Constraint Programming is three steps :
{
// 1) Declare some variables
Int a, b;
// 2) Put some constraints over the variables
1 <= a <= 10;
1 <= b <= 10;
a <= b;
// 3) Get the solutions and use them
cout << solutions(a, b, a+b) << endl;
}
One of the main characteristics of the Constraint Programming paradigm is its
declarative style.
This means you can freely mix/reorder steps 1) and 2) anyhow, provided each variable
is declared before it is referenced in a constraint.
Now, let's examine a few variations of the above code :
{
Int a, b;
1 <= a && a <= 10; // equivalent to 1 <= a <= 10
1 <= b && b <= 10; // equivalent to 1 <= b <= 10
a <= b;
cout << solutions(a, b, a+b) << endl;
}
As you can see, EasyCP lets you freely combine constraints. There is no limitation.
EasyCP provides useful specialized types that help factor some constraints :
{
SInt<1, 10> a, b; // SInt<1, 10> is a Specialized Int type
a <= b;
cout << solutions(a, b, a+b) << endl;
}
The solutions() function is in fact a helper function that returns a typed SolSet object. The previous codes use the default printing ability of the SolSet objects. What if you want to generate your own printing of the solutions, e.g. like the original C++ code ? In these case you have to iterate through the solutions :
{ // C++11 + EasyCP way
SInt<1, 10> a, b;
a <= b;
for (auto & sol : solutions(a, b, a+b))
cout << sol.first() << " + " << sol.second() << " = " << sol.third() << endl;
}
{ // C++98 + EasyCP way
SInt<1, 10> a, b;
a <= b;
typedef SolSet<Int, Int, Int> Sols;
Sols S(a, b, a+b);
for (Sols::iterator iSol = S.begin() ; iSol != S.end() ; ++iSol)
cout << iSol->first() << " + " << iSol->second() << " = " << iSol->third() << endl;
}
Once you get the solutions, you can't constrain the variables anymore.
However, you still can use the variables as a convenient way to print the solutions :
{ // C++11 + EasyCP way
SInt<1, 10> a, b;
a <= b;
Int c = a+b;
for (auto & sol : solutions(a, b, c))
cout << a << " + " << b << " = " << c << endl;
}
{ // C++98 + EasyCP way
SInt<1, 10> a, b;
a <= b;
Int c = a+b;
typedef SolSet<Int, Int, Int> Sols;
Sols S(a, b, c);
for (Sols::iterator iSol = S.begin() ; iSol != S.end() ; ++iSol)
cout << a << " + " << b << " = " << c << endl;
}
The Send More Money problem consists in finding unique digits for the letters D, E, M, N, O, R, S and Y such that S and M are different from zero and the following equation is satisfied:
| S | E | N | D | ||
| + | M | O | R | E | |
| = | M | O | N | E | Y |
Using EasyCP, you can easily solve this by writing something like :
void send_more_money_easy()
{
typedef SInt<0, 9> Digit; // Defines Digit as a Specialized Int type.
Digit S, E, N, D, M, O, R, Y; // Declares some Digit variables.
all_diff(S, E, N, D, M, O, R, Y); // All digits must be different.
1000*S + 100*E + 10*N + D // SEND
+ 1000*M + 100*O + 10*R + E // + MORE
== 10000*M + 1000*O + 100*N + 10*E + Y; // = MONEY
S != 0 && M != 0; // S and M are different from zero
// prints the unique solution, structured with the mT (make_Tuple) function :
// ((9, 5, 6, 7), (1, 0, 8, 5), (1, 0, 6, 5, 2))
cout << solutions(mT(S, E, N, D), mT(M, O, R, E), mT(M, O, N, E, Y));
}
As you can see, the code is quite consise.
Note how each line directly handles one part of the problem description.
At this point, you may feel comfortable with this code.
If you don't, or if you want to see more, just read the following.
The code above is pretty clear, but it contains some redundancy :
Using advanced features of the C++ and EasyCP, it is possible to avoid both points...
Consider :
void send_more_money_advanced()
{
typedef SInt<0, 9> Digit; // Defines Digit as a Specialized Int type.
map<char, Digit> Encoding; // The map that will hold the Digit variables.
Val<Digit> val(Encoding); // Declares a helper function object
val( "SEND") // SEND
+ val( "MORE") // + MORE
== val("MONEY"); // = MONEY
val("S") != 0; // Encoding['S'] is different from zero
val("M") != 0; // Encoding['M'] is different from zero
List<Int> Letters(Encoding); // Puts all the Digit variables in a List
all_diff(Letters); // All the digits must be different
cout << solutions(Letters); // prints the unique solution [7, 5, 1, 6, 0, 8, 9, 2]
// (alphabetical order) D E M N O R S Y
}
Now there is no redundancy anymore !
All what you need to use send_more_money_advanced() is the helper function objet below :
// Helper function objet for send_more_money_advanced // Usage : // map<char, SInt<0, 9> > MyEncoding; // Val<SInt<0, 9> > val(MyEncoding); // ... // val("HEY") --> returns 100*MyEncoding['H'] + 10*MyEncoding['E'] + 1*MyEncoding['Y']; template<class TInt> struct Val { Val(map<char, TInt> & Encoding) : m_Encoding(Encoding) {} IntExpr & operator()(string number, int power = 1) { IntExpr & Res = power * m_Encoding[*number.rbegin()]; number.erase(number.size()-1); if (number.empty()) return Res; else return (*this)(number, power*10) + Res; } map<char, TInt> & m_Encoding; Val & operator=(const Val &); // disabled };
You may think that writing such a helper function object isn't that easy, and you may be right ! The point, though, is that once you got it, you also get this nice function send_more_money_advanced() you can easily refactor...
// solves a + b = c void solve_crypto(const string & a, const string & b, const string & c) { cout << endl << "solving " << a << " + " << b << " = " << c << "..." << endl; typedef SInt<0, 9> Digit; // Defines Digit as a Specialized Int type. map<char, Digit> Encoding; // The map that will hold the Digit variables. Val<Digit> val(Encoding); // Declares a helper function object val(a) + val(b) == val(c); val(a.substr(0, 1)) != 0; val(b.substr(0, 1)) != 0; val(c.substr(0, 1)) != 0; List<Int> Letters(Encoding); // Puts all the Digit variables in a List all_diff(Letters); // All digits must be different cout << solutions(Letters); // prints the solutions }
... so that you can then simply write :
void use_solve_crypto()
{
solve_crypto("SEND", "MORE", "MONEY");
solve_crypto("CROSS", "ROADS", "DANGER");
}
This way of writing small helpers and abstractions effectively leads to better user code. C++ encourages you doing so and EasyCP goes the same way through high integration with both the C++ language and its standard library.
Wikipedia says : Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city ?
An instance of size 5 for the TSP problem
First, let's write a simple function that loads the data of the Distance Matrix :
template<class TList>
istream & operator>>(istream & in, TList & Matrix)
{
const int nb_cities = Matrix.static_size();
for (int y = 0 ; y < nb_cities ; ++y)
for (int x = 0 ; x < nb_cities ; ++x)
{
int n;
in >> n;
Matrix[y][x] == n;
}
return in;
}
EasyCP provides some useful types of variables. One of them is List<T> which is a generic container.
A List holds a fixed number of elements. You must specify its size as an argument in the constructor :
List<Int> L(5); // L is a List of 5 Intsor directly in the type :
SList<Int, 5> L; // SList means Specialized ListFinally, you can use Lists of Lists to represent a matrix, as below :
template<int SIZE>
void solve_tsp(istream & input)
{
SList<SList<Int, SIZE>, SIZE> DistanceMatrix; // Declares the Distance Matrix.
input >> DistanceMatrix; // Loads the Distance Matrix.
typedef SInt<0, SIZE-1> City; // Defines City as a Specialized Int type.
List<City> Route(SIZE); // Declares Route as a List of Cities.
Route[0] == 0; // Say we are looking for routes starting at city #0
all_diff(Route); // Constrains Route to be a Hamiltonian cycle.
List<Int> Distances(SIZE); // Distances lists each distance between
Distances[0] == DistanceMatrix[Route[SIZE-1]][Route[0]]; // two consecutives cities in Route.
for (int i = 1 ; i < SIZE ; ++i)
Distances[i] == DistanceMatrix[Route[i-1]][Route[i]];
Int TotalDistance = sum(Distances); // Defines the total distance of Route.
minimize(TotalDistance); // This is what we want to minimize.
typedef SolSet<List<City>, Int> Sols;
Sols S(Route, TotalDistance);// Let S be the set of the solutions.
for (typename Sols::iterator iSol = S.begin() ; iSol ; ++iSol) // Iterates through S
{
cout << to_string(*iSol) << endl;
}
// In a real case you would exit the loop, based on a certain condition :
// elapsed time, good enough solution found...
}
The important part here is the minimize statement.
Solving an optimization problem requires using either a minimize or a maximize statement.
Such a statement doesn't really constrain any variable.
It influences - though - iteration over the solutions in two ways :
void tsp()
{
cout << endl << "solving the Travelling salesman problem..." << endl;
istringstream input(
" 0 100 125 100 75 \n"
" 100 0 100 75 50 \n"
" 125 100 0 50 125 \n"
" 100 75 50 0 125 \n"
" 75 50 125 125 0 \n"
);
solve_tsp<5>(input);
// Use this syntax to read the data directly from the console :
// solve_tsp<5>(cin);
// Use this syntax to read the data from a file :
// ifstream file("data.txt");
// solve_tsp<5>(file);
}
Output :
([0, 1, 2, 3, 4], 450) ([0, 1, 3, 2, 4], 425) ([0, 2, 3, 1, 4], 375)