algorithm - 给定一组点是否有众所周知的算法填充网格？

Question

我在这里看到了这个游戏Flow ，看起来还蛮有意思​​的。

Connect matching colors with pipe to create a flow. Pair all colors, and cover the entire board to solve each puzzle. But watch out, pipes will break if they cross or overlap.

给定一组对 (x, y)，是否有算法可以解决这个难题，即填充我不知道的整个网格(假设有一个解决方案) ？

Answer 1

这是全局路由问题的一个非常具体的实例。全局布线是 VLSI CAD 中一个经过充分研究的问题(需要在集成电路中布线数百万个网络)。该问题是 NP 完全问题，可以通过多种方式解决，具体取决于您需要在运行时间和质量之间进行权衡。以下 wiki 是一个很好的起点:

https://en.wikipedia.org/wiki/Routing_(electronic_design_automation)

本文对各种技术进行了调查:

http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf

请记住，我给出的指示通常会尝试解决您所陈述问题的复杂得多的版本。尽管如此，数学概念保持不变。