递归实现平方和哈密顿路径代码优化求助

我正在解决Square Sums问题，要求实现一个函数，输入整数N后返回1到N的排列，满足以下两个条件：

• 1到N的每个数字仅使用一次；
• 排列中每两个连续数字的和为完全平方数。

目前我的递归解决方案处理N=1000时耗时约0.7秒，需要把速度提升10倍。测试发现最耗时的操作是每次递归分支中创建新字典的代码：

else:
        possible_nodes  ={key: list(set(values) - {first_one}) for key, values in possible_nodes.items()}

以下是我的完整代码，求优化建议或改进思路：

def square_sums(N):
    def inner(N, done_already=[], filterr=False, possible_nodes={}, options={}, first_one=0):
        if len(done_already) == N - 1:
            left_over = [x for x in range(1, N+1) if x not in done_already][0]
            if (left_over + done_already[-1]) in options:
                done_already.append(left_over)
                return done_already
            else:
                return False
        if not filterr:
            options = {n**2 for n in range(1, int((2*N-1)**0.5) + 1)}
            for pie in range(1, N+1):
                if pie not in done_already:
                    possible_nodes[pie] = [x for x in range(1, N+1) if x+pie in options and x!=pie and x not in done_already]
        else:
            possible_nodes  ={key: list(set(values) - {first_one}) for key, values in possible_nodes.items()}
            possible_nodes.pop(first_one)
            if set() in possible_nodes.values():
                return False
        if not filterr:
            short = min([len(cc) for cc in possible_nodes.values()])
            next_up = [x for x, y in possible_nodes.items() if len(y)==short]
        else:
            grind= [xx for xx in possible_nodes.keys() if (xx+done_already[-1]) in options]
            try:
                short = min([len(cc) for kk, cc in possible_nodes.items() if kk in grind])
                next_up = [x for x,y in possible_nodes.items() if len(y)==short and x in grind]
            except ValueError:
                return False
    
        for possible_path in next_up:
            done_already.append(possible_path)
            if inner(N, done_already, True, possible_nodes, options, possible_path):
                return done_already
            else:
                done_already.pop()
        return False
    return inner(N)

内容的提问来源于stack exchange，提问作者Michael M