Another fun challenge from *Decision Management Community*. A canonical example of the constraint programming (over finite domains) paradigm leads to a simple and elegant SQL solution.

The task is to color a map of six European countries: Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands in such a way that no neighboring countries use the same color. You need to use no more than 4 colors: blue, red, green, or yellow.

Starting with two sets: country and color; who borders whom, and the rule.

country {BE, DK, FR, DE, LU, NL} color {B, R, G, Y} BE borders {FR, LU, DE, NL} DK borders {DE} FR borders {BE, LU, DE} DE borders {FR, LU, BE, NL, DK} LU borders {FR, DE, BE} NL borders {BE, DE} Neighboring countries can not use the same color.

### Reasoning

There are six countries, each one can have one of four colors, so in total there is a maximum of `4^6 = 4096` combinations to examine. The strategy is simple:

- Create a set of all possible combinations.
- Apply constraints.
- Present all results that satisfy given constraints.

The SQL code is straightforward and easy to follow. Try it, there are 144 possible solutions.

## Variation

In a variation of the problem rules are changed a bit. Only three colors are allowed and some neighboring countries are allowed to have the same color, but there is a penalty cost assigned. The task is to find solutions with minimum penalty cost.

country {BE, DK, FR, DE, LU, NL} color {R, G, B} These neighboring countries can use the same color, with assigned cost: LU-FR $257 LU-DE $904 LU-BE $568

### Reasoning v2

This time there are `3^6 = 729` combinations to examine. The strategy:

- Create a set of all possible combinations.
- Apply
*mandatory*constraints. - Calculate the cost for all tuples satisfying mandatory constraints.
- Find the minimum cost.
- Present all results that have the minimum cost.

Again, SQL code is easy to follow, this time there are 12 possible solutions.