棋盘连线算法问题

Question

一个NxN的棋盘，其中有m对棋子，以连线的方式将每一对棋子都连接起来，并保证棋盘被填满。（连接仅能横竖移动，不可交叉，不能跨棋子）

例如给定5x5的棋盘：

0 0 0 4 3
0 0 0 0 0
0 0 1 0 0
0 0 0 2 0
4 2 1 3 0

其中1、2、3、4分别代表棋子，0代表空位（可连线）。期望连接完成之后：

4 4 4 4 3
4 2 2 2 3
4 2 1 2 3
4 2 1 2 3
4 2 1 3 3

其中除了初始点之外的数字都代表线。这里需要注意是“连线”，即每条线必须是有头有尾有顺序的，实际输出结果中也应包含线的每一段的顺序以模拟实际划线过程（谢谢 @felix021 提醒）。化为图形界面大概就是下面这样：

求连接算法或思路，语言不限。

问题补充：本人首先自己写了一个连接算法，是纯粹的递归尝试（因为不是求最短路径，没有用A star），复杂度太高，对小棋盘还好很快出结果（JS在Chrome上几秒之内），但从9x9开始效率惨不忍睹（几十分钟到几个小时-_-#），想了一下没有想到太好的解决方案，求各位帮助啊~~多谢多谢~

Answer 1

我之前写过一个连连看的，和你的问题应该一样，思路是这样的：
1.先判断两点能不能用线段直接连接，能的话问题解决，否则第2步判断。
2.判断两点能不能用仅有一个拐点的折线段连接，能的话问题解决，否则第3步判断。
3.判断两点能不能用仅有两个拐点的折线段连接，能的话问题解决，否则连接不上。
(注：这里说的都是横/竖线段)

假设想要连接的两个点为a、b，算出过a点的横线段A1和过b点的竖线段B1，算出过a点的竖线段A2和过b点的横线段B2
第2步的解决方法：
判断A1、B1能不能相交。不能的话，判断A2、B2能不能相交。
第3步的解决方法：
判断是否有竖线段C1能连接A1和B2，判断是否有横线段C2能连接A2和B1。
－－－－－－－－－－－－－完－－－－－－－－－－－－－－－－－－－

不知道能不能解决你的问题。

Answer 2

感觉像芯片上布线