How could I evaluate the difficulty of a graph-coloring puzzle?

Question

I'm developing a small HTML Canvas & JavaScript based game to train myself and I choose to create a map-colouring puzzle game.

I initially planed to set the puzzle difficulty using the time a given algorithm would take to solve the puzzle but I finally choose to implement a brute-force solving algorithm. The others algorithms were too complicated for me as I didn't found some clear resources where an algorithm for optimal 3- or 4-colourability was well explained.

My issue is some tricky puzzles can be crafted so the brute-force solving take a long time and still the puzzle may be easy with another solving method.

So, how would you determine the relative difficulty of a map-colouring puzzle ?

Answer 1

Your map is a non-oriented graph. The vertices are the surfaces to be filled with colors and the edges are connecting neighbours.
The difficulty of one puzzle is low when you have few number of neighbours on each surface. A hard puzzle is one where each vertex has a lot of edges.
So a way to rank the puzzles would be just:

difficulty = total_number_edges - total_number_vertices

A naive one. You can now improve this formula by adding different other variables like the max number of edges in a vertex or total number of vertices (being that a puzzle with a lot of surfaces to fill is more difficult and takes more time)

difficulty = (total_number_edges - total_number_vertices)  
                        * (total_number_vertices / max_edges_in_vertex)

You should be the inventor of the master-formula :)

Answer 2

the map/graph-coloring problem is "NP-complete". What this means that the scientific community is almost certain that any given algorithm for the problem will spend exponential (huge) amounts of time on certain problem instances (i.e. puzzles). This is why ANY algorithm you implement (incl. your "brute force" mechanism) will choke on some puzzle instances.

What I would recommend is that you implement a couple of different algorithms to solve your puzzles, e.g.

• Algorithm 1 - one by one, choose a random region, and give it a color that still "fits", i.e. is not a color of any colored neighbor. If you run into a conflict (can't color the chosen region), stop the algorithm. Run this loop, say, N times, and calculate the number of times the loop actually colors the whole map; let this be K. Here you get a score K/N (percentage), 0% = hard problem (possibly impossible), 100% = very very easy problem

• Algorithm 2 - add an amount of backtracking to Algorithm 1, e.g. allow for maximum 1,000 backtracking steps. Run the same "sampling" loop. You get another score 0%-100%.

Then use the resulting scores (you would get higher scores from Alg. 2 than from Alg. 1 because it's more powerful) to get the relative difficulty for the puzzles.

The KEY to this whole thing is that if you get score (0%,0%), i.e. you don't know if the puzzles is solvable, you DISCARD it, because you don't want to present your audience problems that might be unsolvable :)

Finally use your own judgement to 'map' the scores to 'human readable' difficulty descriptions --- pick a couple of puzzles, solve them by hand, check the score your program calculates, then see how the percentage scores map to your perception of difficulty.