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.