How could I appreciate the complexity of the graphic coloring puzzle?

Question

I am developing a small HTML version of Canvas and JavaScript for training, and I decided to create a cartographic puzzle game.

I originally planned to establish the complexity of the puzzle using the time this algorithm would take to solve the puzzle, but I finally decided to implement a brute force algorithm. Other algorithms were too complicated for me, since I did not find clear resources where the optimal 3- or 4-color algorithm was well explained.

My problem is some complex puzzles that can be created, so brute force solving takes a lot of time, and still the puzzle can be easily solved using another solution method.

So, how would you determine the relative complexity of a puzzle for coloring cards?

Answer 1

Your map is an undirected graph. Peaks are surfaces filled with flowers, and edges connect neighbors.
The difficulty of one puzzle is low when you have a small number of neighbors on each surface. A tough puzzle is one where each vertex has many edges.
Thus, the way to rank puzzles will be simple:

difficulty = total_number_edges - total_number_vertices 

Naive. Now you can improve this formula by adding various other variables, such as the maximum number of edges in a vertex or the total number of vertices (in that a puzzle with a large number of surfaces to fill is more complicated and takes longer)

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

You must be the inventor of the basic formula :)

Answer 2

map / graph display issue "NP-complete". This means that the scientific community is almost certain that any given problem algorithm will spend exponential (huge) amounts of time on specific instances of the problem (i.e.Puzzles). This is why any algorithm you implement (including your brute force mechanism) will overwhelm some puzzle examples.

I would recommend that you implement a couple of different algorithms to solve your puzzles, for example.

• Algorithm 1 - one by one, select a random area and give it a color that is still "suitable", i.e. is not the color of any color neighbor. If you encounter a conflict (cannot paint the selected area), stop the algorithm. Run this cycle, say, N times, and count the number of cycles that actually actually color the entire map; let it be K. Here you get the K / N score (in percent), 0% = difficult problem (possibly impossible), 100% = very simple problem

• Algorithm 2 - add the amount of backtracking to algorithm 1, for example. allow a maximum of 1000 indentation steps. Run the same “fetch” cycle. You get one more point 0% -100%.

Then use the resulting points (you will get higher points from Alg. 2 than from Alg.1 because they are more powerful) to get the relative difficulty for the puzzles.

The key to this is that if you get a score (0%, 0%), that is, you don’t know if the puzzles are solvable, YOU REFUSE it because you don’t want to present problems to your audience, it can be unsolvable :)

Finally, use your own judgment to “match” scores with “readable” descriptions of difficulties — select a couple of puzzles, solve them manually, check the score your program calculates, and then see how percentages are mapped to your perception of difficulty.

Answer 3

I found a paragraph that gave me an idea of ​​how you could appreciate the difficulty.

One class of approximation algorithms based on the "greedy" method - vertices are processed in order, with each vertex being assigned the lowest numbered class of colors, which does not put it in conflict with its previously painted neighbors. Because vertices adjacent to the current vertex can use all four colors, the fifth or even the sixth, seventh, etc. color may be required. When the greedy method is to create a new class of colors, the vertex is called impasee.

Thus, the number of color classes needed can be a difficulty for your puzzle. You can handle the vertices, for example. from highest to lowest (most ordered ordering scheme)

I found the paragraph in article A Fast probabilistic algorithm for four-color large planar graphs by Raymond A. Archulet and Henry D. Shapiro