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.

Data Table: Bordering Countries
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:

Number of models: 1
Model 1
=======
structure  : V {
  Country_borders_Country = { Belgium,France; Belgium,Germany; Belgium,Luxembourg; Belgium,Netherlands; France,Luxembourg; Germany,Denmark; Germany,France; Germany,Luxembourg; Netherlands,Germany }
  Color = { Belgium->Yellow; Denmark->Red; France->Green; Germany->Orange; Luxembourg->Red; Netherlands->Green }
}

Elapsed Time:
0.052835

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