如何系统排列1-15使相邻两数之和为平方数？

嘿，别再靠瞎猜碰运气啦！这个问题完全可以用图论的思路系统性解决，一步一步来就很清晰～

第一步：把数字转化成图的节点和边 #

我们可以把1到15的每个数字看作一个节点，如果两个数字的和是平方数（比如1+3=4=2²、3+13=16=4²），就给这两个节点连一条边。

先整理出每个数字能配对的伙伴：

• 1：3、8、15
• 2：7、14
• 3：1、6、13
• 4：5、12
• 5：4、11
• 6：3、10
• 7：2、9
• 8：1
• 9：7
• 10：6、15
• 11：5、14
• 12：4、13
• 13：3、12
• 14：2、11
• 15：1、10

第二步：锁定路径的起点/终点 #

观察每个节点的“连接数”（度数）：8和9的度数都是1，这意味着它们必须是路径的起点或终点——因为度数为1的节点只能在路径的两端，没法在中间（中间节点需要有进有出，至少两条边）。

第三步：找完整的哈密顿路径 #

现在问题就变成了在这个图里找一条哈密顿路径（经过每个节点恰好一次的路径），从8或9出发就行：

比如从8开始的有效路径：
8 → 1 → 15 → 10 → 6 → 3 → 13 → 12 → 4 → 5 → 11 → 14 → 2 → 7 → 9

验证一下相邻和：

• 8+1=9=3²，1+15=16=4²，15+10=25=5²
• 10+6=16=4²，6+3=9=3²，3+13=16=4²
• 13+12=25=5²，12+4=16=4²，4+5=9=3²
• 5+11=16=4²，11+14=25=5²，14+2=16=4²
• 2+7=9=3²，7+9=16=4²

反过来从9出发也完全可行：9→7→2→14→11→5→4→12→13→3→6→10→15→1→8

系统性方法总结 #

1. 把数字建模成图：数字=节点，和为平方数=连边
2. 定位特殊节点：度数为1的节点只能是路径两端，缩小起始范围
3. 用深度优先搜索（DFS）遍历：从特殊节点出发，按边的连接逐步探索，比瞎猜高效N倍

内容的提问来源于stack exchange，提问作者J Tg