用SQL求下面的序列

〇〇

还是真人写的厉害，把https://github.1git.de/FluorineDog/square_sum 改造一下
40-100几秒钟就全出来了

newkid

用SQL实现了？

〇〇

不是sql，是一个叫sage的

1. 
   
2. def getgraph(n,N,path):
   
3.     powers=[(i+1)^N for i in range(ceil((2*n)^(1/N)))]
   
4.     G=Graph()
   
5.     G.add_vertices([1,..,n])
   
6.     edges=[]
   
7.     for p in powers:
   
8.         for i in range(1,ceil(p/2)+1):
   
9.             if i<=n and p-i<=n and p-i>0 and i!=p-i:    #add i!=p-i
   
10.                 edges.append([i,p-i])
    
11. 
    
12.     if path:   #add an extra vertex connected to all others
    
13.         G.add_vertex(0)  #to get path from cycle
    
14.         for i in [1,..,n]:
    
15.             edges.append([0,i])
    
16.     G.add_edges(edges)
    
17.     return G
    
18. 
    
19. 
    
20. 
    
21. #n=100
    
22. N=2
    
23. for n in range(32, 301):
    
24.     path=False
    
25.     G=getgraph(n,N,path)
    
26.     hami=G.hamiltonian_cycle()
    
27.     l=hami.cycle_basis()[0]
    
28.     print (n, [l[(i+l.index(int(not(path))))%len(l)] for i in range(len(l))])
    
29. 
    

复制代码

〇〇

通过和deepseek合作，我说思路，他编代码。达到了sage的速度

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. #include <cmath>
   
5. #include <ctime>
   
6. #include <bitset>
   
7. #include <algorithm>
   
8. 
   
9. using namespace std;
   
10. 
    
11. const int MAX_N = 500;  // 假设最大顶点数为 100
    
12. 
    
13. class Graph {
    
14.     int V;  // 顶点数
    
15.     vector<bitset<MAX_N>> adj;  // 邻接表（使用 bitset 表示）
    
16. public:
    
17.     Graph(int V) : V(V), adj(V) {}
    
18.     long long cnt = 0;
    
19. 
    
20.     void add_edge(int u, int v) {
    
21.         adj[u].set(v);  // 设置 u 和 v 之间的边
    
22.         adj[v].set(u);  // 无向图，双向设置
    
23.     }
    
24. 
    
25.     bool hamiltonian_cycle_util(vector<int>& path, bitset<MAX_N>& visited, int pos, int start) {
    
26.         if (pos == V) {
    
27.             // 检查是否形成环
    
28.             if (adj[path[pos - 1]].test(start)) {
    
29.                 return true;
    
30.             }
    
31.             return false;
    
32.         }
    
33. 
    
34.         // 获取当前顶点的邻接顶点 bitset
    
35.         bitset<MAX_N> neighbors = adj[path[pos - 1]] & ~visited;
    
36. 
    
37.         // 提取所有未访问的邻接顶点
    
38.         vector<int> neighbor_list;
    
39.         for (int v = neighbors._Find_first(); v < MAX_N; v = neighbors._Find_next(v)) {
    
40.             neighbor_list.push_back(v);
    
41.         }
    
42. 
    
43.         // 按未使用的邻接点数量排序
    
44.         sort(neighbor_list.begin(), neighbor_list.end(), [this, &visited](int a, int b) {
    
45.             return (adj[a] & ~visited).count() < (adj[b] & ~visited).count();
    
46.         });
    
47. 
    
48.         // 遍历排序后的邻接顶点
    
49.         for (int v : neighbor_list) {
    
50.             // 如果未到最后一步，且 v 是起点的最后一个邻接点，则跳过
    
51.             if (pos != V - 1 && v == start && adj[path[pos - 1]].count() == 1) {
    
52.                 continue;
    
53.             }
    
54. 
    
55.             cnt++;
    
56.             if (cnt > 100000) {  // 如果递归调用次数超过 10 万，直接返回 false
    
57.                 return false;
    
58.             }
    
59. 
    
60.             path[pos] = v;
    
61.             visited.set(v);  // 标记为已访问
    
62.             if (hamiltonian_cycle_util(path, visited, pos + 1, start)) {
    
63.                 return true;
    
64.             }
    
65.             visited.reset(v);  // 回溯
    
66.         }
    
67.         return false;
    
68.     }
    
69. 
    
70.     vector<int> hamiltonian_cycle() {
    
71.         vector<int> path(V, -1);
    
72.         bitset<MAX_N> visited;  // 使用 bitset 存储访问状态
    
73. 
    
74.         // 尝试从每个起点开始
    
75.         for (int s = 0; s < V; s++) {
    
76.             cnt = 0;  // 重置递归调用次数
    
77.             path.assign(V, -1);  // 重置路径
    
78.             visited.reset();  // 重置访问状态
    
79. 
    
80.             // 从顶点 s 开始
    
81.             path[0] = s;
    
82.             visited.set(s);
    
83. 
    
84.             if (hamiltonian_cycle_util(path, visited, 1, s)) {
    
85.                 return path;
    
86.             }
    
87.         }
    
88.         return {};
    
89.     }
    
90. };
    
91. 
    
92. int main() {
    
93.     // 测试 n 从 80 到 100
    
94.     for (int n = 301; n <= 500; n++) {
    
95.         Graph G(n);
    
96. 
    
97.         // 构建图
    
98.         for (int i = 1; i <= n; ++i) {
    
99.             for (int j = i + 1; j <= n; ++j) {
    
100.                 int sum = i + j;
     
101.                 int sqrt_sum = sqrt(sum);
     
102.                 if (sqrt_sum * sqrt_sum == sum) {
     
103.                     G.add_edge(i - 1, j - 1);  // 顶点编号从 0 开始
     
104.                 }
     
105.             }
     
106.         }
     
107. 
     
108.         // 基于当前系统的当前日期/时间
     
109.         time_t now = time(0);
     
110. 
     
111.         // 查找哈密顿环
     
112.         vector<int> cycle = G.hamiltonian_cycle();
     
113.         if (!cycle.empty()) {
     
114.             cout << "n = " << n << ": Hamiltonian Cycle found. Recursive calls: " << G.cnt << ", Time: " << time(0) - now << " seconds." << endl;
     
115.             cout << "Cycle: ";
     
116.             for (int v : cycle) {
     
117.                 cout << v + 1 << " ";  // 恢复顶点编号
     
118.             }
     
119.             cout << endl;
     
120.         } else {
     
121.             cout << "n = " << n << ": No Hamiltonian Cycle found. Recursive calls: " << G.cnt << ", Time: " << time(0) - now << " seconds." << endl;
     
122.         }
     
123.     }
     
124. 
     
125.     return 0;
     
126. }
     

复制代码

〇〇

https://oeis.org/A090461 指向的引用 https://www.mersenneforum.org/node/17331/ 说证明了当n>=25哈密顿路径都存在，n>=32哈密顿回路都存在借助deepseek 和sage,运行了其中的代码。大概知道怎么从n=35 的已知哈密顿回路得到n=35*25+12=887 的解。
把1-12挑出来，再把1-35每个数*25+（-12到12）得到其他数（比如1得到13-27，35得到863-887），为了保持相邻和是平方数，相邻数分别+-（-1），它的和=25*（a(i)+a(i+1)+1-1)仍然是平方数。
然后把35组序列和1-12粘贴起来，使得粘贴处符合和平方要求。

〇〇

让deepseek分别生成了 https://www.mersenneforum.org/node/17331/ 中的思路和 c++程序思路的python 代码，还是前者快一点

1. 
   
2. import math
   
3. from collections import defaultdict
   
4. 
   
5. def generate_vertices(b):
   
6.     """生成顶点集合（单元素数组 + 35元素数组及其翻转）"""
   
7.     vertices = []
   
8.     # 单元素顶点（1-12）
   
9.     for c in range(1, 13):
   
10.         vertices.append({
    
11.             "array": [c],
    
12.             "type": "single",
    
13.             "c": c,
    
14.             "reversed": False,
    
15.             "id": f"single_{c}"
    
16.         })
    
17.     # 35元素顶点（c从-12到12，包括0）
    
18.     for c in range(-12, 13):
    
19.         v = [25 * b[i] + c * ((-1) ** i) for i in range(len(b))]
    
20.         vertices.append({
    
21.             "array": v,
    
22.             "type": "complex",
    
23.             "c": c,
    
24.             "reversed": False,
    
25.             "id": f"c{c}_orig"
    
26.         })
    
27.         vertices.append({
    
28.             "array": v[::-1],
    
29.             "type": "complex",
    
30.             "c": c,
    
31.             "reversed": True,
    
32.             "id": f"c{c}_rev"
    
33.         })
    
34.     return vertices
    
35. 
    
36. def is_square_sum(a, b):
    
37.     """检查两个数之和是否为完全平方数"""
    
38.     s = a + b
    
39.     return s >= 0 and int(math.sqrt(s)) ** 2 == s
    
40. 
    
41. def build_adjacency_list(vertices):
    
42.     """构建邻接表并预计算原始度数"""
    
43.     adj = defaultdict(list)
    
44.     degrees = defaultdict(int)
    
45.     for i, u in enumerate(vertices):
    
46.         for j, v in enumerate(vertices):
    
47.             if i == j:
    
48.                 continue
    
49.             if is_square_sum(u["array"][-1], v["array"][0]):
    
50.                 adj[i].append(j)
    
51.                 degrees[i] += 1  # 记录原始度数
    
52.     return adj, degrees
    
53. 
    
54. def dynamic_degree(current, adj, visited):
    
55.     """动态计算邻接节点的有效度数（未使用的邻接数）"""
    
56.     neighbor_degrees = []
    
57.     for neighbor in adj[current]:
    
58.         if neighbor in visited:
    
59.             continue
    
60.         # 计算该邻居未使用的邻接数
    
61.         valid_links = sum(1 for n in adj[neighbor] if n not in visited)
    
62.         neighbor_degrees.append( (neighbor, valid_links) )
    
63.    
    
64.     # 按有效度数升序排序
    
65.     return sorted(neighbor_degrees, key=lambda x: x[1])
    
66. 
    
67. def backtrack_search(vertices, adj, degrees, max_steps=1e6):
    
68.     """优化后的回溯搜索，优先选择低度数节点"""
    
69.     # 定位起点[1]和终点[3]
    
70.     start = next(i for i, v in enumerate(vertices) if v["c"] == 1 and v["type"] == "single")
    
71.     end = next(i for i, v in enumerate(vertices) if v["c"] == 3 and v["type"] == "single")
    
72.    
    
73.     # 初始化状态跟踪
    
74.     visited = set([start])
    
75.     path = [start]
    
76.     used_single = {1}
    
77.     used_c = set()
    
78.     step_counter = [0]
    
79.     result = None
    
80.    
    
81.     def recurse(current, used_single, used_c):
    
82.         step_counter[0] += 1
    
83.         if step_counter[0] > max_steps:
    
84.             print(step_counter[0])
    
85.             return "overflow"
    
86.         
    
87.         # 终止条件：12个单元素 + 25个35元素数组
    
88.         if len(path) == 37:  # 12单元素 + 25复杂数组
    
89.             if current == end and is_square_sum(vertices[path[-1]]["array"][-1], vertices[path[0]]["array"][0]):
    
90.                 return path.copy()
    
91.             return None
    
92.         
    
93.         # 动态计算当前邻接节点的有效度数并排序
    
94.         neighbors = dynamic_degree(current, adj, visited)
    
95.         
    
96.         # 优先尝试低度数节点
    
97.         for neighbor, _ in neighbors:
    
98.             vertex = vertices[neighbor]
    
99.             
    
100.             # 检查顶点使用规则
     
101.             if vertex["type"] == "single":
     
102.                 if vertex["c"] in used_single:
     
103.                     continue
     
104.                 new_used_single = used_single | {vertex["c"]}
     
105.                 new_used_c = used_c
     
106.             else:
     
107.                 if vertex["c"] in used_c:
     
108.                     continue
     
109.                 new_used_c = used_c | {vertex["c"]}
     
110.                 new_used_single = used_single
     
111.             
     
112.             # 提前剪枝：最后一步必须是终点
     
113.             if len(path) == 36 and neighbor != end:
     
114.                 continue
     
115.             
     
116.             # 更新状态
     
117.             visited.add(neighbor)
     
118.             path.append(neighbor)
     
119.             ret = recurse(neighbor, new_used_single, new_used_c)
     
120.             
     
121.             if ret == "overflow":
     
122.                 return ret
     
123.             if ret is not None:
     
124.                 return ret
     
125.             
     
126.             # 回溯
     
127.             path.pop()
     
128.             visited.remove(neighbor)
     
129.         
     
130.         return None
     
131.    
     
132.     # 执行搜索
     
133.     result = recurse(start, used_single, used_c)
     
134.    
     
135.     if result == "overflow":
     
136.         print(f"达到最大递归次数 {max_steps}，未找到解")
     
137.         return None
     
138.     return [vertices[i]["array"] for i in result] if result else None
     
139. 
     
140. # ---------- 执行程序 ----------
     
141. if __name__ == "__main__":
     
142.     # 输入参数
     
143.     b = [1,8,28,21,4,32,17,19,6,30,34,15,10,26,23,13,12,24,25,11,5,20,29,35,14,2,7,18,31,33,16,9,27,22,3]
     
144.    
     
145.     # 生成图结构
     
146.     vertices = generate_vertices(b)
     
147.     adj, degrees = build_adjacency_list(vertices)
     
148.    
     
149.     # 执行搜索（可根据需要调整max_steps）
     
150.     path = backtrack_search(vertices, adj, degrees, max_steps=500_000)
     
151.    
     
152.     if path:
     
153.         print("找到哈密顿回路：")
     
154.         full_path=[]
     
155.         for i, arr in enumerate(path):
     
156.             full_path+=arr
     
157.             #print(f"Step {i+1}: {arr}")
     
158.         print(full_path)
     
159.     else:
     
160.         print("未找到有效路径")
     
161. 
     

复制代码

c++思路

1. 
   
2. import math
   
3. import time
   
4. from collections import defaultdict
   
5. 
   
6. class Graph:
   
7.     def __init__(self, V):
   
8.         self.V = V  # 顶点数
   
9.         self.adj = [0] * V  # 邻接表（使用位运算表示）
   
10.         self.cnt = 0  # 递归计数器
    
11. 
    
12.     def add_edge(self, u, v):
    
13.         """添加边（无向图）"""
    
14.         self.adj[u] |= 1 << v
    
15.         self.adj[v] |= 1 << u
    
16. 
    
17.     def hamiltonian_cycle_util(self, path, visited, pos, start):
    
18.         """回溯工具函数，寻找哈密顿回路"""
    
19.         self.cnt += 1
    
20.         if self.cnt > 100_000:  # 递归次数超过 100,000 次，直接返回
    
21.             return False
    
22. 
    
23.         # 终止条件：路径包含所有顶点且首尾相连
    
24.         if pos == self.V:
    
25.             if self.adj[path[pos - 1]] & (1 << start):
    
26.                 return True
    
27.             return False
    
28. 
    
29.         # 获取当前顶点的未访问邻接顶点
    
30.         neighbors = self.adj[path[pos - 1]] & ~visited
    
31. 
    
32.         # 按未使用的邻接点数量排序（动态度数排序）
    
33.         neighbor_list = []
    
34.         for v in range(self.V):
    
35.             if neighbors & (1 << v):
    
36.                 # 计算 v 的未使用邻接点数量
    
37.                 valid_links = bin(self.adj[v] & ~visited).count("1")
    
38.                 neighbor_list.append((v, valid_links))
    
39. 
    
40.         # 按未使用的邻接点数量升序排序
    
41.         neighbor_list.sort(key=lambda x: x[1])
    
42. 
    
43.         # 尝试每个邻接顶点
    
44.         for v, _ in neighbor_list:
    
45.             # 如果未到最后一步，且 v 是起点的最后一个邻接点，则跳过
    
46.             if pos != self.V - 1 and v == start and bin(self.adj[path[pos - 1]]).count("1") == 1:
    
47.                 continue
    
48. 
    
49.             path[pos] = v
    
50.             visited |= 1 << v  # 标记为已访问
    
51.             if self.hamiltonian_cycle_util(path, visited, pos + 1, start):
    
52.                 return True
    
53.             visited &= ~(1 << v)  # 回溯
    
54. 
    
55.         return False
    
56. 
    
57.     def hamiltonian_cycle(self):
    
58.         """寻找哈密顿回路"""
    
59.         path = [-1] * self.V
    
60.         visited = 0  # 使用位运算表示访问状态
    
61. 
    
62.         # 尝试从每个起点开始
    
63.         for s in range(self.V):
    
64.             self.cnt = 0  # 重置递归计数器
    
65.             path = [-1] * self.V
    
66.             visited = 0
    
67. 
    
68.             # 从顶点 s 开始
    
69.             path[0] = s
    
70.             visited |= 1 << s
    
71. 
    
72.             if self.hamiltonian_cycle_util(path, visited, 1, s):
    
73.                 return path
    
74. 
    
75.         return None
    
76. 
    
77. # ---------- 主程序 ----------
    
78. if __name__ == "__main__":
    
79.     # 输入参数
    
80.     n = 887  # 顶点数
    
81.     b = [1, 8, 28, 21, 4, 32, 17, 19, 6, 30, 34, 15, 10, 26, 23, 13, 12, 24, 25, 11, 5, 20, 29, 35, 14, 2, 7, 18, 31, 33, 16, 9, 27, 22, 3]
    
82. 
    
83.     # 生成图
    
84.     G = Graph(n)
    
85. 
    
86.     # 构建图（根据平方和规则添加边）
    
87.     for i in range(1, n + 1):
    
88.         for j in range(i + 1, n + 1):
    
89.             s = i + j
    
90.             sqrt_s = int(math.isqrt(s))
    
91.             if sqrt_s * sqrt_s == s:
    
92.                 G.add_edge(i - 1, j - 1)  # 顶点编号从 0 开始
    
93. 
    
94.     # 计时开始
    
95.     start_time = time.time()
    
96. 
    
97.     # 查找哈密顿回路
    
98.     cycle = G.hamiltonian_cycle()
    
99. 
    
100.     # 计时结束
     
101.     elapsed_time = time.time() - start_time
     
102. 
     
103.     # 输出结果
     
104.     if cycle:
     
105.         print(f"哈密顿回路找到！递归调用次数: {G.cnt}, 耗时: {elapsed_time:.2f} 秒")
     
106.         print("回路:", [v + 1 for v in cycle])  # 恢复顶点编号
     
107.     else:
     
108.         print(f"未找到哈密顿回路。递归调用次数: {G.cnt}, 耗时: {elapsed_time:.2f} 秒")
     

复制代码

〇〇

把deepseek的c++和数学论坛方法结合起来，加入了我自己的优化，主要是# 动态计算邻接节点的有效度数并排序 减少了循环次数

1. 
   
2. import math
   
3. from collections import defaultdict
   
4. 
   
5. def generate_vertices(b):
   
6.     """生成顶点集合（单元素数组 + 35元素数组及其翻转）"""
   
7.     vertices = []
   
8.     # 单元素顶点（1-12）
   
9.     for c in range(1, 13):
   
10.         vertices.append({
    
11.             "array": [c],
    
12.             "type": "single",
    
13.             "c": c,
    
14.             "reversed": False,
    
15.             "id": f"single_{c}"
    
16.         })
    
17.     # 35元素顶点（c从-12到12，包括0）
    
18.     for c in range(-12, 13):
    
19.         v = [25 * b[i] + c * ((-1) ** i) for i in range(len(b))]
    
20.         vertices.append({
    
21.             "array": v,
    
22.             "type": "complex",
    
23.             "c": c,
    
24.             "reversed": False,
    
25.             "id": f"c{c}_orig"
    
26.         })
    
27.         vertices.append({
    
28.             "array": v[::-1],
    
29.             "type": "complex",
    
30.             "c": c,
    
31.             "reversed": True,
    
32.             "id": f"c{c}_rev"
    
33.         })
    
34.     return vertices
    
35. 
    
36. def is_square_sum(a, b):
    
37.     """检查两个数之和是否为完全平方数"""
    
38.     s = a + b
    
39.     return s >= 0 and int(math.sqrt(s)) ** 2 == s
    
40. 
    
41. def build_adjacency_list(vertices):
    
42.     """构建邻接表并预计算原始度数（位图形式）"""
    
43.     adj = [0] * 62  # 总顶点数为62（12单元素 + 50复杂元素）
    
44.     degrees = defaultdict(int)
    
45.     for i, u in enumerate(vertices):
    
46.         for j, v in enumerate(vertices):
    
47.             if i == j:
    
48.                 continue
    
49.             if is_square_sum(u["array"][-1], v["array"][0]):
    
50.                 adj[i] |= (1 << j)  # 位图标记邻接关系
    
51.                 degrees[i] += 1
    
52.     return adj, degrees
    
53. 
    
54. def backtrack_search(start, vertices, adj, degrees, max_steps=1e5):
    
55.     """优化后的回溯搜索（邻接表使用位图）"""
    
56.     # 初始化状态跟踪
    
57.     visited = 1 << start  # 位图表示已访问节点
    
58.     path = [start]
    
59.     used_single = {start}
    
60.     used_c = set()
    
61.     step_counter = [0]
    
62.     result = None
    
63.    
    
64.     def recurse(current, used_single, used_c):
    
65.         nonlocal visited
    
66.         step_counter[0] += 1
    
67.         if step_counter[0] > max_steps:
    
68.             return "overflow"
    
69.         
    
70.         # 终止条件：路径包含37个节点（12单元素 + 25复杂元素）
    
71.         if len(path) == 37:
    
72.             last_node = vertices[path[-1]]["array"][-1]
    
73.             first_node = vertices[path[0]]["array"][0]
    
74.             if is_square_sum(last_node, first_node):
    
75.                 return path.copy()
    
76.             return None
    
77.         
    
78.         # 动态计算邻接节点的有效度数并排序
    
79.         bi = adj[current] & (~visited)  # 当前节点的未访问邻接位图
    
80.         empty_list = []
    
81.         while bi != 0:
    
82.             rt = bi & (-bi)             # 提取**有效位
    
83.             p = pndic[rt]               # 获取位对应的索引
    
84.             bi = bi & (bi - 1)          # 清除**有效位
    
85.             empty_list.append(p)
    
86.         
    
87.         # 计算每个邻接节点的有效度数
    
88.         dynamic_degree = []
    
89.         for v in empty_list:
    
90.             valid_links = bin(adj[v] & ~visited).count("1")  # 位运算统计有效邻接数
    
91.             dynamic_degree.append((v, valid_links))
    
92.         
    
93.         # 按有效度数升序排序
    
94.         neighbors = sorted(dynamic_degree, key=lambda x: x[1])
    
95.         
    
96.         # 优先尝试低度数节点
    
97.         for neighbor, _ in neighbors:
    
98.             vertex = vertices[neighbor]
    
99.             
    
100.             # 检查顶点使用规则
     
101.             if vertex["type"] == "single":
     
102.                 if vertex["c"] in used_single:
     
103.                     continue
     
104.                 new_used_single = used_single | {vertex["c"]}
     
105.                 new_used_c = used_c
     
106.             else:
     
107.                 if vertex["c"] in used_c:
     
108.                     continue
     
109.                 new_used_c = used_c | {vertex["c"]}
     
110.                 new_used_single = used_single
     
111.             
     
112.             # 更新状态
     
113.             visited |= (1 << neighbor)
     
114.             path.append(neighbor)
     
115.             ret = recurse(neighbor, new_used_single, new_used_c)
     
116.             
     
117.             if ret == "overflow":
     
118.                 return ret
     
119.             if ret is not None:
     
120.                 return ret
     
121.             
     
122.             # 回溯
     
123.             path.pop()
     
124.             visited &= ~(1 << neighbor)
     
125.         
     
126.         return None
     
127.    
     
128.     # 执行搜索
     
129.     result = recurse(start, used_single, used_c)
     
130.    
     
131.     if result == "overflow":
     
132.         return None
     
133.     return [vertices[i]["array"] for i in result] if result else None
     
134. 
     
135. # ---------- 主程序 ----------
     
136. if __name__ == "__main__":
     
137.     # 输入参数
     
138.     b = [1,8,28,21,4,32,17,19,6,30,34,15,10,26,23,13,12,24,25,11,5,20,29,35,14,2,7,18,31,33,16,9,27,22,3]
     
139.    
     
140.     # 预计算二进制位到索引的映射字典（pndic）
     
141.     pndic = {1 << i: i for i in range(100)}  # 例如：pndic[8] = 3, 因为 8 = 2^3
     
142.    
     
143.     # 生成图结构
     
144.     vertices = generate_vertices(b)
     
145.     adj, degrees = build_adjacency_list(vertices)
     
146.    
     
147.     # 执行搜索（可根据需要调整max_steps）
     
148.     path = None
     
149.     for start in range(1, 62):  # 尝试从每个顶点开始
     
150.         path = backtrack_search(start, vertices, adj, degrees, max_steps=5_000)
     
151.         if path:
     
152.             break
     
153.    
     
154.     if path:
     
155.         print("找到哈密顿回路：")
     
156.         full_path = []
     
157.         for arr in path:
     
158.             full_path += arr
     
159.         print("完整序列长度:", len(full_path))
     
160.         print("示例序列（前20个元素）:", full_path[:20])
     
161.     else:
     
162.         print("未找到有效路径")
     
163. 
     

复制代码

〇〇

umbradb比duckdb快很多

1. 
   
2. with recursive t(i) as (select * from generate_series(1,36)),
   
3. s(s) as (select i*i from t where i*i<36+36),
   
4. a(a,b,c)as (select t.i,t1.i,t.i+t1.i from t,t t1 where t.i<>t1.i and t.i+t1.i in (select s from s)),
   
5. c(lv,l,r,bmp,path)
   
6. as(select 1,1,a.b, (1::bigint<<(1-1))+(1::bigint<<(a.b-1)),array[1,a.b] from a where a.a=1
   
7. union all
   
8. select lv+1,c.r,a.b, bmp + (1::bigint<<(a.b-1)),path||array[a.b]from c,a where a.a=c.r and bmp & (1::bigint<<(a.b-1))=0 and lv<35)
   
9. select * from c where lv=35 and 1+c.r in (select s from s) ;
   

复制代码

duckdb 1.1.3
│ 62 rows (40 shown)
Run Time (s): real 2.194 user 7.090761 sys 1.481828

umbradb v0.2-1145-ge323595be (2025-03-24, format 40)

INFO:    execution: (0.718814 min, 0.718814 max, 0.718814 median, 0.0% relMAD, 0.718814 avg, 0.000000 sdev, 2 scale, nan IPC, nan CPUs, nan GHz) compilation: (0.003111 min, 0.003111 max, 0.003111 median, 0.0% relMAD, 0.003111 avg, 0.000000 sdev)

〇〇

umbradb 38就内存不足了，duckdb能算出来
[code]
umbra@01fee55f0c23:/var/db$ umbra-sql
> with recursive t(i) as (select * from generate_series(1,38)),
i from t where i*i<38+38),
a(s(s) as (select i*i from t where i*i<38+38),
> a(a,b,c)as (select t.i,t1.i,t.i+t1.i from t,t t1 where t.i<>t1.i and t.i+t1.i in (select s from s)),
> c(lv,l,r,bmp,path)
> as(select 1,1,a.b, (1::bigint<<(1-1))+(1::bigint<<(a.b-1)),array[1,a.b] from a where a.a=1
> union all
reselect lv+1,c.r,a.b, bmp + (1::bigint<<(a.b-1)),path||array[a.b]from c,a where a.a=c.r and bmp & (1::bigint<<(a.b-1))=0 and lv<38-1)
> select * from c where lv=38-1 and 1+c.r in (select s from s) ;
lv l r bmp path
ERROR:   unable to allocate memory
> \q
D with recursive t(i) as (select * from generate_series(1,38)),
  s(s) as (select i*i from t where i*i<38+38),
  a(a,b,c)as (select t.i,t1.i,t.i+t1.i from t,t t1 where t.i<>t1.i and t.i+t1.i in (select s from s)),
  c(lv,l,r,bmp,path)
  as(select 1,1,a.b, (1::bigint<<(1-1))+(1::bigint<<(a.b-1)),array[1,a.b] from a where a.a=1
  union all
  select lv+1,c.r,a.b, bmp + (1::bigint<<(a.b-1)),path||array[a.b]from c,a where a.a=c.r and bmp & (1::bigint<<(a.b-1))=0 and lv<38-1)
  select * from c where lv=38-1 and 1+c.r in (select s from s) ;
Run Time (s): real 8.793 user 27.807343 sys 5.329259
[code]