如何在矩阵中为配对彩色节点寻找不相交且填满矩阵的路径？

我有一个包含多组彩色节点的矩阵，每个节点都属于一对同色节点。核心目标是将每个节点与其配对节点用路径连接，且必须满足以下约束：

• 所有路径互不相交
• 仅允许上下左右的正交移动
• 路径需填满矩阵的全部单元格

示例场景：

对应的解决方案：

目前我采用回溯递归算法实现，逻辑是依次尝试为每个节点规划移动路径，直到完成所有配对连接，还针对左→下→右这类低效折返路径做了简单优化。该方案虽然能得到正确结果，但时间复杂度极高——就连上述示例都需要约半分钟才能执行完成。

想请教两个问题：

1. 是否应该采用多流图方法来优化算法效率？
2. 这个问题本身是否不存在多项式时间级别的高效解决方案？

该问题与Stack Overflow上的相关问题类似，但目前尚未有明确结论。

内容的提问来源于stack exchange，提问作者Анастасия Разумовская