我怎样才能评估图形着色拼图的难度？

Question

我正在开发一个基于HTML Canvas和JavaScript的小游戏来训练自己,我选择创建一个地图着色益智游戏.

我最初计划使用给定算法解决难题所需的时间来设置难题,但我最终选择实施强力求解算法.其他算法对我来说太复杂了,因为我没有找到一些明确的资源,其中很好地解释了最佳3或4色可靠性的算法.

我的问题是可以制作一些棘手的谜题,因此蛮力解决需要很长时间,而且使用另一种解决方法仍然可以轻松解决难题.

那么,您如何确定地图着色拼图的相对难度？

Answer 1

你的地图是一个无向图。顶点是要填充颜色的表面，边缘是连接邻居的表面。
当每个表面上的邻居数量很少时，一个谜题的难度就会很低。硬谜题是指每个顶点都有很多边的谜题。
因此，对谜题进行排名的方法就是：

difficulty = total_number_edges - total_number_vertices

一个天真的人。现在，您可以通过添加不同的其他变量来改进此公式，例如顶点中的最大边数或顶点总数（因为需要填充大量曲面的谜题更加困难并且需要更多时间）

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

你应该是主公式的发明者:)