Map Coloring

The map coloring problem is a common problem. We will show how to solve it using only cDMN. The full DMCommunity challenge, with other submitted solutions can be found here.

Map Coloring Challenge

This challenge deals with map coloring. You need to use no more than 4 colors (blue, red, green, or yellow) to color six European countries: Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands in such a way that no neighboring countries use the same color.

We start by creating our glossary. For this specific problem, the glossary does not need to be complex. We create a type to represent countries and a type to represent the colors.

Type
Name	Type	Values
Country	String	Belgium, France, Germany, Luxembourg, Netherlands
Color	String	Green, Red, Yellow, Orange

To assign every country exactly one color, we can use a function. To express that two countries border, we use a relation.

Function
Name	Type
color of Country	Color

Relation
Name
Country borders Country

Now that our glossary is done, we can move on to the next step: modeling the problem logic. This logic is very simple: if two countries border, they cannot share the same color. We can represent this straightforwardly using a constraint table. The table is read as: “For every two countries c1, c2, if they border they cannot share the same color.”

Bordering countries cannot share colors
E*	Country called c1	Country called c2	c1 borders c2	color of c1
1	-	-	Yes	Not(color of c2)

And that is all the logic we need to solve this problem! We simply need to represent which countries border which using a data table, and we’re done.

Bordering Countries
D	Country called c1	Country called c2	c1 borders c2
1	Belgium	France, Luxembourg, Netherlands, Germany	Yes
2	Netherlands	Germany	Yes
3	Germany	France, Luxembourg, Denmark	Yes
4	France	Luxembourg	Yes

We can now run our model using the cDMN solver. This results in the following output:

Model 1
==========
color_of_Country := {Belgium->Yellow, France->Red, Luxembourg->Green, Netherlands->Green, Germany->Orange, Denmark->Green}.
Country_borders_Country := {(Belgium,France), (Belgium,Luxembourg), (Belgium,Netherlands), (Belgium,Germany), (France,Luxembourg), (Netherlands,Germany), (Germany,France), (Germany,Luxembourg), (Germany,Denmark)}.

Elapsed Time:
0.902

We are now able to color a map without having to worry about bordering countries sharing a color!