I am making a game where you have to colour an image using the 4-colour theorem. No adjacent regions can be the same colour. There are four colours (red, green, blue, and yellow) and you get 10 points for each red region, 6 for green, 3 for blue and 1 for yellow. I want an algorithm to work out the maximum score for any given image. I extract a planar graph from the image, which gives for each region, a list of its neighbours.
My brute force implementation checks all possible colourings, which grows like 4**n for n regions. I can optimise this as much as possible but is there any faster way? For 2 colours there is a linear time algorithm but for game design reasons I will not generate images which can be coloured with 2 colours.
Here are some example Python dictionaries. Their keys are the region id's and the lists are the list of neighbours of that region:
easy = {2: [4], 4: [2, 3, 14, 13], 3: [4], 14: [4], 13: [4]}
Top score: 46 (I think), my Python brute force: 0.1s.
medium = {2: [4, 5, 6], 4: [2, 3], 3: [4, 18], 5: [2, 6], 6: [5, 2, 13, 18], 13: [6, 20, 21, 22], 18: [6, 3, 20, 22], 20: [18, 13], 22: [18, 13], 21: [13]}
Top score: 77, my Python brute force: 7.2s.
hard = {2: [5, 6, 9], 5: [2, 4], 4: [5, 23], 6: [2, 7, 10], 3: [8, 16], 8: [3, 7, 12], 7: [6, 8, 10, 11], 9: [2, 10], 10: [6, 9, 7, 13, 14, 15, 17, 18], 11: [7, 12, 13], 12: [8, 11, 15, 16, 19], 13: [10, 11, 15], 14: [10, 15], 15: [10, 13, 12, 14, 17, 19], 16: [3, 12, 25, 27], 17: [10, 15, 18], 18: [10, 17, 19, 20], 19: [15, 18, 12, 27], 20: [18, 22, 24, 26, 27, 25], 22: [20], 23: [4, 24, 26], 24: [23, 20], 25: [16, 20], 26: [23, 20], 27: [19, 20, 16]}
My Python brute force: unknown.
Here is my try on the problem. I was not able to come up with a better time complexity but optimized the brute-force.
I processed the nodes one-by-one only allowing for colorings such that no two neighbor nodes have the same color.
I added an upper bound estimation for each intermediate (non complete) coloring. For this I assumed that every non-colored node will be colored in the highest-scoring color (only allowing different colors than the already colored neighbours). So in the upper bound calculation two adjacent nodes that have not been colored yet could both be colored "red". With this estimation I built a branch-and-bound algorithm, that terminates the current search-path when the upper-bound estimation is still lower than the current maximum.
The runtime for the small graph is less than 1 ms, for the medium graph it is 15 ms and for the large graph 3.2 seconds. The results for the three graphs are 46, 77 and 194, respectively.
import time
import copy
def upperBoundScore(graph, dfsGraphOder, dfsIndex, coloring, scoring, currentScore):
maxAdditionalScore = 0;
for i in range(dfsIndex, len(dfsGraphOder)):
neighbourColors = {coloring[node] for node in graph[dfsGraphOder[i]]}
possibleColors = {1, 2, 3, 4} - neighbourColors
if len(possibleColors) < 1: # if for one node no color is available stop
return -1
maxAdditionalScore += scoring[list(possibleColors)[0]]
return currentScore+maxAdditionalScore
def colorRemainingGraph(graph, dfsGraphOder, dfsIndex, coloring, scoring, currentScore):
global maxScore
global bestColoring
# whole graph colored
if dfsIndex == len(dfsGraphOder):
if currentScore > maxScore:
maxScore = currentScore
bestColoring = copy.deepcopy(coloring)
# only proceed if current coloring can get better then best coloring
elif upperBoundScore(graph, dfsGraphOder, dfsIndex, coloring, scoring, currentScore) > maxScore:
neighbourColors ={coloring[node] for node in graph[dfsGraphOder[dfsIndex]]}
possibleColors = list({1, 2, 3, 4} - neighbourColors)
for c in possibleColors:
coloring[dfsGraphOder[dfsIndex]] = c
currentScore += scoring[c]
colorRemainingGraph(graph, dfsGraphOder, dfsIndex+1, coloring, scoring, currentScore)
currentScore -= scoring[c]
coloring[dfsGraphOder[dfsIndex]] = 0
#graph = {2: [4], 4: [2, 3, 14, 13], 3: [4], 14: [4], 13: [4]}
#graph = {2: [4, 5, 6], 4: [2, 3], 3: [4, 18], 5: [2, 6], 6: [5, 2, 13, 18], 13: [6, 20, 21, 22], 18: [6, 3, 20, 22], 20: [18, 13], 22: [18, 13], 21: [13]}
graph = {2: [5, 6, 9], 5: [2, 4], 4: [5, 23], 6: [2, 7, 10], 3: [8, 16], 8: [3, 7, 12], 7: [6, 8, 10, 11], 9: [2, 10], 10: [6, 9, 7, 13, 14, 15, 17, 18], 11: [7, 12, 13], 12: [8, 11, 15, 16, 19], 13: [10, 11, 15], 14: [10, 15], 15: [10, 13, 12, 14, 17, 19], 16: [3, 12, 25, 27], 17: [10, 15, 18], 18: [10, 17, 19, 20], 19: [15, 18, 12, 27], 20: [18, 22, 24, 26, 27, 25], 22: [20], 23: [4, 24, 26], 24: [23, 20], 25: [16, 20], 26: [23, 20], 27: [19, 20, 16]}
# 0 = uncolored, 1 = red, 2 = green, 3 = blue, 4 = Yellow
scoring = {1:10, 2:6, 3:3, 4:1}
coloring = {node: 0 for node in graph.keys()}
nodeOrder = list(graph.keys())
maxScore = 0
bestColoring = {}
start = time.time()
colorRemainingGraph(graph, nodeOrder, 0, coloring, scoring, 0)
end = time.time()
print("Runtime: "+ str(end - start))
print("Max Score: "+str(maxScore))
print(bestColoring)
For the large graph the resulting coloring is (1 = red, 2 = green, 3 = blue, 4 = yellow):
{2: 1, 3: 1, 4: 1, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2, 10: 3, 11: 2, 12: 1, 13: 1, 14: 1, 15: 4, 16: 2, 17: 2, 18: 1, 19: 2, 20: 2, 22: 1, 23: 2, 24: 1, 25: 1, 26: 1, 27: 1}
To verify that the coloring outputed by the algorithm is correct one can use the below code, which checks if any two neighbor nodes have the same color.
def checkSolution(graph, coloring):
validColoring=1
for node in graph:
for neighbour in graph[node]:
if coloring[node] == coloring[neighbour]:
print("wrong coloring found "+ str(node) + " and " + str(neighbour) + " have the same color")
validColoring = 0
if validColoring:
print("Coloring is valid")