How can this planar map be coloured using $4$ colours?
This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.
The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.
The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.
That gives a rather simpler map to colour.