.. _map_coloring: 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. `_ .. admonition:: 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. .. raw:: html

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. .. raw:: html

Function
Name	Type
color of Country	Color

.. raw:: html

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." .. raw:: html

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. .. raw:: html

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: .. code:: bash 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!