Efficient algorithm for planar 4-colour graph colouring with scoring

Question

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 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 be able to work out the maximum score for any given image. I have the code for extracting a planar graph from the image, which gives, for each region, a list of it's neighbours.

So far I have done a brute force implementation which checks all possible colourings, however that grows like 4**n for n regions. One approach I can take is to try and optimise this search as much as possible.

Is there any faster way? I know for 2 colours there is a linear time algorithm however for game design reasons I will generally not generate images which can be coloured with 2 colours.

Thanks :)

Edit: as sascha requests here are some example python dicts, they 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 bruteforce 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 bruteforce 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 bruteforce unknown)

Edit2:

So I finished the game, if you are interested you can check it out here.

For the sake of the game I realized I only needed a high score rather than the absolute top score (which is what the question asked for). So I implemented greedy colouring and ran it 10,000 times shuffling the graph each time and taking the best scoring result. On all small boards of less than 30 regions this produces the same result as the brute force methods however it's time complexity scales much better to larger boards. So it may not find the absolutely best solution it will always find a very good one.

Thanks so much to @SaiBot and @sascha for their help :)

SaiBot · Accepted Answer

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")

Efficient algorithm for planar 4-colour graph colouring with scoring

Answers (2)

Code (python3; numpy, scipy, cylp + CoinOR Cbc solver)

Output

Results

Transfer

Related Questions