Map Coloring

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:

1. Create a set of all possible combinations.
2. Apply constraints.
3. 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:

1. Create a set of all possible combinations.
2. Apply mandatory constraints.
3. Calculate the cost for all tuples satisfying mandatory constraints.
4. Find the minimum cost.
5. Present all results that have the minimum cost.

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

A challenge by Decision Management Community.

A zoo has four monkeys, during the monkey lunchtime each one ate a different fruit in their favourite resting place. Sam, who doesn’t like bananas, likes sitting on the grass. The monkey who sat on the rock ate the apple. The monkey who ate the pear didn’t sit on the tree branch. Anna sat by the stream but she didn’t eat the pear. Harriet didn’t sit on the tree branch. Mike doesn’t like oranges.

1. What kind of fruit each monkey ate?
2. Where their favourite resting place was?

So, how to solve this in SQL? It is easy to identify domains, predicates and rules; after that it is straightforward. Continue reading “Monkey Business”

Eight Years on SO

After eight years on StackOverflow and more than 600 answers, these are my favourite three.

1. How to understand the fifth normal form? [🔗]
2. Composite primary key vs. an additional ID column. [🔗]
3. How to design this database to avoid the cyclic dependency? [🔗]

These are not the highest voted answers, but I like them. All three rely on basic time-tested knowledge and principles, favour simplicity and reasoning over confusion and technical trickery.

Rule 25

Introducing a new tag on the blog named Rule 25. For a post to qualify, the content, knowledge and principles presented must be valid not only today, but were valid at least 25 years ago, and I firmly believe will be valid for at least the next 25 years.
In contrast to current versions of this-and-that, skills and knowledge that do not survive a year.