Tag Archives: algorithm

Learn from previously colored maps

Posted on by
Reply

Stay with me 👀, because this is going to like you.

I came up with an idea that feels so simple and obvious that I can’t help but wonder why I hadn’t thought of it earlier. Maybe difficult to implement 😭 but the idea it is good and simple.

I’m curious if anyone has explored something similar, or if there are known related results 🤔

Would love to hear your thoughts!

I’ve been working on the Four Color Theorem 🎨, specifically on reducing planar 3-regular graphs down to a minimal configuration and then back reconstructing them step by step using, when necessary, different color Kempe chain switches techniques.

The challenge is that while my reduction strategy works in most cases ✅, there are configurations where the reconstruction gets stuck ❌ and Kempe switches don’t resolve the conflict. Only by shuffling the order of face selection 🔀 I’ve always been able to eventually color the map.

Here’s the idea 🚀: instead of trying to design the perfect reduction strategy upfront, why not start from the opposite direction?

Since I can already color arbitrarily complex graphs (even if it requires trial, backtracking, and random Kempe switches 🎲), I can treat successful colorings as “ground truth”.

From there, I can analyze the sequence of reductions on an already colored graph and observe which choices preserve a valid path back to a full coloring 🔍

In other words, rather than guessing the best reduction strategy, I can learn it from examples of graphs that have already been four-colored.

Four color theorem: A fast algorithm – 2

Posted on by
Reply

Four color theorem: A fast algorithm

These are the OLD and NEW (last column) execution times on my new laptop:

  • 100 – 196 vertices, 294 edges = 0 seconds – 0 seconds
  • 200 – 396 vertices, 594 edges = 1 seconds – 0 seconds
  • 300 – 596 vertices, 894 edges = 4 seconds – 1 second
  • 400 – 796 vertices, 1194 edges = 6 seconds – 1 second
  • 500 – 996 vertices, 1494 edges = 8 seconds – 2 seconds
  • 600 – 1196 vertices, 1794 edges = 10 seconds – 4 seconds
  • 700 – 1396 vertices, 2094 edges = 16 seconds – 6 seconds
  • 800 – 1596 vertices, 2394 edges = 18 seconds – 7 seconds
  • 900 – 1796 vertices, 2694 edges = 22 seconds – 9 seconds
  • 1000 – 1996 vertices, 2994 edges = 26 seconds – 11 seconds

Four color theorem: deep analysis of a map

Posted on by
Reply

I would like to implement a brute force algorithm to search ALL the different colorings of a map.

Here is the question on: math.stackexchange.com

In terms of graph theory I’d like to find all four colorings of the vertices of a planar graph (the dual representing the map).

I’m interested in maps in which each face is an opaque rectangle layered on all previous rectangles, overlapping partially. Each consecutive rectangle starts at a consecutive y coordinate. The next picture should better clarify what I mean.

The faces are numbered from 1 to n

  • face 1 is the face on the bottom of the pile
  • face (n-1) is the face at the top
  • face n is the infinite face surrounding all others

For the meaning of different colorings you can refer to this question: mathoverflow.net

I was thinking to pre-set the colors of faces and use a classical brute force algorithm to get four coloring of the map. I already implemented the brute force algorithm to find the proper coloring of a map and I can also force the color of faces to find particolar colorings.

The problem is that I’m not coming up with an algorithm to do it automatically and to be sure to find ALL colorings.

To see what I have so far, you can watch this video on youtube:

!

What I know is that:

  • Since the colors of three neighbors faces can be arbitrary, face number n, face number 1 and the face touching both (face n and face 1), can have these fixed colors: blue, red, green

Manually I found these colorings: