Four color theorem with Prolog

On this post I’ll talk about the four color theorem and how to solve it using Prolog, this is a very common exercise when you start studying Prolog and you can find a lot of examples on the internet with small maps, this examples can be easily replicated to large maps, on this example I’ll use the map of Brazil that contains 27 federative units.

Four Color Theorem

How many different colors you think are sufficient to color a map considering that you can’t use the same color on two adjacent regions? Let’s imagine that you want to color the world map with this rule, how many pencils do you need? This is already solved and you need only four colors! This is the four color theorem.

“In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet.”

A good curiosity is that four color theorem can only be proved by computers.

Example:

Four color theorem example

Solving

To solve it, as the title of the text describes, we will use Prolog a programming language that applies the logic paradigm of programming, I already wrote about an if you are interested you can check here.

Brazil Map

We will apply this theorem on Brazil map, I chose the Brazil map because, with 27 federative units, it can be considered a large map, but the algorithm that we’ll be used can be replicated to any map.

Brazil Map

Solving the Problem

The first thing that we can do is to transform Brazil map in a graph to see more clearly which states are adjacent.

Brazil States Graph

After this we already know our facts that Prolog need to solve our problem, the first thing that we can do is to choose four colors to paint our map, just declare the facts:

color(black).
color(byzantine).
color(sapphire_blue).
color(screamin_green).

After this the next thing that we can do is to write the rule of two adjacent states, this rule needs to tell Prolog that two states can’t have the same color.

adjacent(State1Color, State2Color) :-
    color(State1Color), color(State2Color),
    State1Color \= State2Color.

Explaining the code: On the first part of the rule we declare that the rule names are adjacent and that it will receive two states as params called State1Color and State2Color, after this, we give a color for states and a rule that these colors can’t be the same.

This rule is simple, it receives two states, give a color to them respecting the rule that colors can’t be the same. With all these steps done we can write all the adjacent states as facts.

We can test our rule on some region of our graph, for this, I chose these regions that in my opinion is a complex region:

Complex region of Brazil graph

Now, just make a query asking for Prolog solve it using or adjacent rule:

?- adjacent(TO, BA), adjacent(TO, GO), adjacent(TO, MT),
   adjacent(BA, GO), adjacent(BA, MG), adjacent(BA, ES),
       adjacent(BA, SE), adjacent(BA, AL), adjacent(BA, PE),
   adjacent(PE, AL), adjacent(AL, SE),
   adjacent(MG, ES), adjacent(MG, GO), adjacent(MG, DF),
   adjacent(GO, DF), adjacent(GO, MT).

And the output result will be:

AL = ES, ES = GO, GO = sapphire_blue,
BA = DF, DF = MT, MT = byzantine,
MG = PE, PE = SE, SE = TO, TO = black

After this, we can paint our graph and conclude that it is correct:

Complex region of Brazil colored with four colors

Ok, now we know that our rule is working as expected, we have two options or we make a query passing all adjacent states (like the one that we did before but all states), or we code a rule and just call this rule as a query. I think that the first option is equal to the previous example, so let’s create a rule to paint the Brazil map, this rule is very simple, it’s only map all adjacent states and put inside a rule:

brazil(AC, AM, PA, RR, RO, AP, MT,
       MA, TO, GO, MS, DF,
       PI, CE, RN, PB, PE, AL,
       SE, BA, ES, MG, RJ,
       SP, PR, SC, RS) :-
    adjacent(AC, AM), adjacent(AC, RO),
    adjacent(AM, RO), adjacent(AM, RR), adjacent(AM, PA),
        adjacent(AM, MT),
    adjacent(PA, RR), adjacent(PA, AP), adjacent(PA, MA),
        adjacent(PA, TO), adjacent(PA, MT),
    adjacent(RO, MT),
    adjacent(MT, TO), adjacent(MT, GO), adjacent(MT, MS),
    adjacent(MA, PI), adjacent(MA, TO),
     adjacent(TO, PI), adjacent(TO, BA), adjacent(TO, GO),
    adjacent(GO, BA), adjacent(GO, MG), adjacent(GO, MS), adjacent(GO, DF),
    adjacent(MS, MG), adjacent(MS, SP), adjacent(MS, PR),
    adjacent(DF, MG),
    adjacent(PI, CE), adjacent(PI, PE), adjacent(PI, BA),
    adjacent(CE, RN), adjacent(CE, PB), adjacent(CE, PE),
    adjacent(RN, PB),
    adjacent(PB, PE),
    adjacent(PE, AL), adjacent(PE, BA),
    adjacent(AL, SE), adjacent(AL, BA),
    adjacent(SE, BA),
    adjacent(BA, MG), adjacent(BA, ES),
    adjacent(ES, MG), adjacent(ES, RJ), adjacent(MG, SP),
    adjacent(MG, RJ), adjacent(MG, SP),
    adjacent(RJ, SP),
    adjacent(SP, PR),
    adjacent(PR, SC),
    adjacent(SC, RS).

This rule only receive 27 federation units, map them as adjacent and will output the colors, now we just need to make a query passing the states on the correct order:

brazil(AC, AM, PA, RR, RO, AP, MT,
       MA, TO, GO, MS, DF,
       PI, CE, RN, PB, PE, AL,
       SE, BA, ES, MG, RJ,
       SP, PR, SC, RS).

And the first result output will be:

AC = AP, AP = BA, BA = CE, CE = DF, DF = MA, MA = MT, MT = RR, RR = SC, SC = SP, SP = black,
AL = GO, GO = PA, PA = PB, PB = PI, PI = PR, PR = RJ, RJ = RO, RO = sapphire_blue,
AM = ES, ES = MS, MS = PE, PE = RN, RN = RS, RS = SE, SE = TO, TO = byzantine,
MG = screamin_green

After some minutes painting our map, I got:

Brazil map colored with four colors

The map is correct and a fun fact about this solution is that only one state needs screamin_green color.

Our experiment is done, but another question can be answered now, how many different solutions it has? We only used the first solution that Prolog has given to us. Fortunately, we have a way to calculate it, just use the predicate aggregate_all/3 and it will count how many results it finds.

?- aggregate_all(count, brazil(AC, AM, PA, RR, RO, AP, MT, MA, TO, GO, MS, DF, PI, CE,
      RN, PB, PE, AL, SE, BA, ES, MG, RJ, SP, PR, SC, RS), Count).

And the result is huge:

Count = 384860160.

three hundred eighty-four million, eight hundred sixty thousand, one hundred sixty of combinations found.

And finally, we finished our experiment.

Conclusion

As I said in my last post about logic programming here, Prolog is worth learning, and for solving this kind of problem it shines but you’ll need to expend a lot of time giving the facts (as we did with adjacent states).

Final thought

If you have any question that I can help you, please ask! Send an email (otaviopvaladares@gmail.com), pm me on my Twitter or comment on this post!

Follow my blog to get notified every new post:

Automate the boring stuff with Python review

A few weeks ago I finished reading “Automate the boring stuff with Python” from Al Sweigart, In this review, I’ll try to make a good review of the book and talk about the main chapters.

It’s a book recommended for novices, for me, it’s a good book for beginners, but for people who already know how to program in other dynamic and interpreted programming language, I think is not necessary to read this book, go ahead and read something more advanced.

TL;DR: If you know how to program in another interpreted programming language like Ruby, go ahead and read something more advanced, if you are a beginner, start with this book, it’s a very good book to start coding.

If you want to know more about this book, you can check here: https://automatetheboringstuff.com/

Print / Publisher

The book publisher is the famous no starch press, that have a lot of famous books like:

And much more, I think every experienced programmer knows nostarch very well because they have a lot of famous and good books, if you are a beginner, you can trust them.

I didn’t have the physical edition of this book, I’ve read the digital edition on my Kindle Paperwhite, read technical books on digital readers is always it’s always a fear because some books don’t look good at the small screens, especially the code snippets, but this was not the problem of this book, I think large publishers like nostarch or O’Reilly you’ll never going to have this problem.

The physical edition I think should be excellent too, because I have other books from nostarch and no one disappointed me.

Content

The book is divided into two parts, the first one talks about all the basic things of any programming language like variables, loops, ifs/else and etc. This part is good to understand the basic of python. This part covers all between variables and manipulates text.

The second part and the most interesting show you how to automate boring stuff with python in a simple way, at this part you develop a lot of applications, for example reading Excel documents. This part has eleven chapters, talking about a lot of things, this is the best part of my opinion, the author shows you how to do a lot of cool things like web scraping 🙂

Final Conclusions

The most interesting is the second part when you create a lot of applications to automate the boring stuff, but the first part is good to understand and knows the python basic. One thing that I loved in this book is the fact that it has a lot of exercises (with answers) to you train what you learned in the chapter, if you do all the exercises your read will be funnier and you’ll learn much more.

The only bad thing on this book is that this is a simple book for people that already know how to program, but this is not a problem because the book doesn’t say that is something advanced, but even for who already knows how to program, the second part with practical projects can be very good.

Final thoughts

This is my first book review and I’ll try to get better on the next review posts, I’ll try to review every technical book that I read.

If you want to know more about this book, you can check here: https://automatetheboringstuff.com/

If you have any question that I can help you, please ask! Send an email (otaviopvaladares@gmail.com), pm me on my Twitter or comment on this post!

Follow my blog to get notified every new post: