2026年4月1日 研究日志¶
今日研究内容：整理实验数据和有关代码。因为今天没有什么实质性进展，发几个今天收拾出来的以前拿来玩的代码吧。
↓当年了解了冰雹猜想后试着画着玩的图。这个论述起来相当简单的猜想（对于所有正整数N，如果是偶数就除以2，是奇数就3N+1，最后总归会呈现4-2-1的循环），现在却仍得不到证明，不得不说数学真是高深啊。
In [1]:
%matplotlib inline
import matplotlib.pyplot as plt
def Collatz(n):
global m_list,n_list
m = 0
n_list = [n]
while n != 1:
if n % 2 == 1:
n = 3 * n + 1
n_list.append(n)
m += 1
else:
n = n/2
n_list.append(n)
m += 1
m_list = range(m+1)
return m_list,n_list
Collatz(26)
x1 = m_list
y1 = n_list
print('对于26而言，共有{}轮雹程'.format(max(m_list)))
print('最大值为{}。'.format(max(n_list)))
Collatz(27)
x2 = m_list
y2 = n_list
print('对于27而言，共有{}轮雹程'.format(max(m_list)))
print('最大值为{}。'.format(max(n_list)))
plt.plot(x1,y1,color='red',linewidth=1.0,linestyle='-')
plt.plot(x2,y2,color='blue',linewidth=1.0,linestyle='-')
plt.show()
对于26而言，共有10轮雹程 最大值为40.0。 对于27而言，共有111轮雹程 最大值为9232.0。
↓N皇后问题 没想到一个突发奇想的问题竟然如此的复杂。说起来我其实没玩过国际象棋，皇后可太能走了，横竖斜的。搞这个主要是我在参与BOINC平台的yoyo@home项目中，看到有解这个的。参加这个项目都已经五年了。说起来我还发现了一个ecm factors呢（25556569658706368570429153）。圆锥曲线相关的东西可太难了，我这个临床医学背景的还是不敢碰的（笑）
In [3]:
def solve_n_queens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queen(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queen(n, index + 1, ocuppied_positions + [pos])
return result
return place_queen(n, 0, [])
print(solve_n_queens(8))
[[0, 4, 7, 5, 2, 6, 1, 3], [0, 5, 7, 2, 6, 3, 1, 4], [0, 6, 3, 5, 7, 1, 4, 2], [0, 6, 4, 7, 1, 3, 5, 2], [1, 3, 5, 7, 2, 0, 6, 4], [1, 4, 6, 0, 2, 7, 5, 3], [1, 4, 6, 3, 0, 7, 5, 2], [1, 5, 0, 6, 3, 7, 2, 4], [1, 5, 7, 2, 0, 3, 6, 4], [1, 6, 2, 5, 7, 4, 0, 3], [1, 6, 4, 7, 0, 3, 5, 2], [1, 7, 5, 0, 2, 4, 6, 3], [2, 0, 6, 4, 7, 1, 3, 5], [2, 4, 1, 7, 0, 6, 3, 5], [2, 4, 1, 7, 5, 3, 6, 0], [2, 4, 6, 0, 3, 1, 7, 5], [2, 4, 7, 3, 0, 6, 1, 5], [2, 5, 1, 4, 7, 0, 6, 3], [2, 5, 1, 6, 0, 3, 7, 4], [2, 5, 1, 6, 4, 0, 7, 3], [2, 5, 3, 0, 7, 4, 6, 1], [2, 5, 3, 1, 7, 4, 6, 0], [2, 5, 7, 0, 3, 6, 4, 1], [2, 5, 7, 0, 4, 6, 1, 3], [2, 5, 7, 1, 3, 0, 6, 4], [2, 6, 1, 7, 4, 0, 3, 5], [2, 6, 1, 7, 5, 3, 0, 4], [2, 7, 3, 6, 0, 5, 1, 4], [3, 0, 4, 7, 1, 6, 2, 5], [3, 0, 4, 7, 5, 2, 6, 1], [3, 1, 4, 7, 5, 0, 2, 6], [3, 1, 6, 2, 5, 7, 0, 4], [3, 1, 6, 2, 5, 7, 4, 0], [3, 1, 6, 4, 0, 7, 5, 2], [3, 1, 7, 4, 6, 0, 2, 5], [3, 1, 7, 5, 0, 2, 4, 6], [3, 5, 0, 4, 1, 7, 2, 6], [3, 5, 7, 1, 6, 0, 2, 4], [3, 5, 7, 2, 0, 6, 4, 1], [3, 6, 0, 7, 4, 1, 5, 2], [3, 6, 2, 7, 1, 4, 0, 5], [3, 6, 4, 1, 5, 0, 2, 7], [3, 6, 4, 2, 0, 5, 7, 1], [3, 7, 0, 2, 5, 1, 6, 4], [3, 7, 0, 4, 6, 1, 5, 2], [3, 7, 4, 2, 0, 6, 1, 5], [4, 0, 3, 5, 7, 1, 6, 2], [4, 0, 7, 3, 1, 6, 2, 5], [4, 0, 7, 5, 2, 6, 1, 3], [4, 1, 3, 5, 7, 2, 0, 6], [4, 1, 3, 6, 2, 7, 5, 0], [4, 1, 5, 0, 6, 3, 7, 2], [4, 1, 7, 0, 3, 6, 2, 5], [4, 2, 0, 5, 7, 1, 3, 6], [4, 2, 0, 6, 1, 7, 5, 3], [4, 2, 7, 3, 6, 0, 5, 1], [4, 6, 0, 2, 7, 5, 3, 1], [4, 6, 0, 3, 1, 7, 5, 2], [4, 6, 1, 3, 7, 0, 2, 5], [4, 6, 1, 5, 2, 0, 3, 7], [4, 6, 1, 5, 2, 0, 7, 3], [4, 6, 3, 0, 2, 7, 5, 1], [4, 7, 3, 0, 2, 5, 1, 6], [4, 7, 3, 0, 6, 1, 5, 2], [5, 0, 4, 1, 7, 2, 6, 3], [5, 1, 6, 0, 2, 4, 7, 3], [5, 1, 6, 0, 3, 7, 4, 2], [5, 2, 0, 6, 4, 7, 1, 3], [5, 2, 0, 7, 3, 1, 6, 4], [5, 2, 0, 7, 4, 1, 3, 6], [5, 2, 4, 6, 0, 3, 1, 7], [5, 2, 4, 7, 0, 3, 1, 6], [5, 2, 6, 1, 3, 7, 0, 4], [5, 2, 6, 1, 7, 4, 0, 3], [5, 2, 6, 3, 0, 7, 1, 4], [5, 3, 0, 4, 7, 1, 6, 2], [5, 3, 1, 7, 4, 6, 0, 2], [5, 3, 6, 0, 2, 4, 1, 7], [5, 3, 6, 0, 7, 1, 4, 2], [5, 7, 1, 3, 0, 6, 4, 2], [6, 0, 2, 7, 5, 3, 1, 4], [6, 1, 3, 0, 7, 4, 2, 5], [6, 1, 5, 2, 0, 3, 7, 4], [6, 2, 0, 5, 7, 4, 1, 3], [6, 2, 7, 1, 4, 0, 5, 3], [6, 3, 1, 4, 7, 0, 2, 5], [6, 3, 1, 7, 5, 0, 2, 4], [6, 4, 2, 0, 5, 7, 1, 3], [7, 1, 3, 0, 6, 4, 2, 5], [7, 1, 4, 2, 0, 6, 3, 5], [7, 2, 0, 5, 1, 4, 6, 3], [7, 3, 0, 2, 5, 1, 6, 4]]
↓用回溯法解数独。当时学习了八皇后问题后发现了回溯算法这种有趣的算法，就想到可以用在数独上了，没想到还挺复杂折腾了一段时间。
In [4]:
from copy import deepcopy
# 9x9 数独，0 表示空格
Grid = list[list[int]]
def print_grid(grid: Grid):
for i, row in enumerate(grid):
print(" ".join(str(x) if x != 0 else "." for x in row))
if i % 3 == 2 and i != 8:
print("-" * 21)
def get_block_index(row, col):
return (row // 3) * 3 + (col // 3)
def init_candidates(grid: Grid):
"""
为每个格子初始化候选集合：candidates[(r, c)] = {1..9} 或已缩小的集合
"""
candidates = {}
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
blocks = [set() for _ in range(9)]
# 先记录已有数字
for r in range(9):
for c in range(9):
val = grid[r][c]
if val != 0:
rows[r].add(val)
cols[c].add(val)
blocks[get_block_index(r, c)].add(val)
# 初始化候选
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
used = rows[r] | cols[c] | blocks[get_block_index(r, c)]
candidates[(r, c)] = set(range(1, 10)) - used
else:
candidates[(r, c)] = set()
return candidates
def find_mrv_cell(candidates):
"""
MRV：找到候选数最少的未填格子
"""
mrv_cell = None
mrv_size = 10
for (r, c), cand in candidates.items():
if len(cand) > 0 and len(cand) < mrv_size:
mrv_size = len(cand)
mrv_cell = (r, c)
return mrv_cell
def propagate(grid: Grid, candidates):
"""
简单约束传播：
- 若某格子只剩一个候选数，则直接填入
- 填入后更新相关格子的候选集
若出现某格子候选集为空且未填值 → 冲突，返回 False
"""
changed = True
while changed:
changed = False
singles = [(cell, next(iter(cand)))
for cell, cand in candidates.items()
if len(cand) == 1]
if not singles:
break
for (r, c), val in singles:
if grid[r][c] != 0:
continue
grid[r][c] = val
candidates[(r, c)] = set()
changed = True
# 更新同行、同列、同宫候选
for rr in range(9):
if (rr, c) in candidates and val in candidates[(rr, c)]:
candidates[(rr, c)].remove(val)
if len(candidates[(rr, c)]) == 0 and grid[rr][c] == 0:
return False
for cc in range(9):
if (r, cc) in candidates and val in candidates[(r, cc)]:
candidates[(r, cc)].remove(val)
if len(candidates[(r, cc)]) == 0 and grid[r][cc] == 0:
return False
br = (r // 3) * 3
bc = (c // 3) * 3
for rr in range(br, br + 3):
for cc in range(bc, bc + 3):
if (rr, cc) in candidates and val in candidates[(rr, cc)]:
candidates[(rr, cc)].remove(val)
if len(candidates[(rr, cc)]) == 0 and grid[rr][cc] == 0:
return False
return True
def is_complete(grid: Grid):
return all(all(cell != 0 for cell in row) for row in grid)
def solve_sudoku(grid: Grid):
"""
回溯 + MRV + 前向检查 + 约束传播
"""
candidates = init_candidates(grid)
if not propagate(grid, candidates):
return None
def backtrack(grid, candidates):
if is_complete(grid):
return grid
cell = find_mrv_cell(candidates)
if cell is None:
return None
r, c = cell
for val in sorted(candidates[(r, c)]):
new_grid = deepcopy(grid)
new_cand = deepcopy(candidates)
new_grid[r][c] = val
new_cand[(r, c)] = set()
# 前向检查：更新相关候选
for rr in range(9):
if (rr, c) in new_cand and val in new_cand[(rr, c)]:
new_cand[(rr, c)].remove(val)
for cc in range(9):
if (r, cc) in new_cand and val in new_cand[(r, cc)]:
new_cand[(r, cc)].remove(val)
br = (r // 3) * 3
bc = (c // 3) * 3
for rr in range(br, br + 3):
for cc in range(bc, bc + 3):
if (rr, cc) in new_cand and val in new_cand[(rr, cc)]:
new_cand[(rr, cc)].remove(val)
# 约束传播
if not propagate(new_grid, new_cand):
continue
res = backtrack(new_grid, new_cand)
if res is not None:
return res
return None
return backtrack(grid, candidates)
In [5]:
puzzle = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
]
print("Puzzle:")
print_grid(puzzle)
solution = solve_sudoku(puzzle)
print("\nSolution:")
print_grid(solution)
Puzzle: 5 3 . . 7 . . . . 6 . . 1 9 5 . . . . 9 8 . . . . 6 . --------------------- 8 . . . 6 . . . 3 4 . . 8 . 3 . . 1 7 . . . 2 . . . 6 --------------------- . 6 . . . . 2 8 . . . . 4 1 9 . . 5 . . . . 8 . . 7 9 Solution: 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 --------------------- 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 --------------------- 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
↓忙海狸问题 当时5海狸问题得到解的时感到有些兴趣所以试了试。说起来除了NP问题，还有更多问题连验证都没有办法在多项式时间内完成呢。这世间真是有太多事情得不到答案了呢。
In [6]:
class TuringMachine:
def __init__(self, rules, start_state="A", blank=0):
"""
rules: dict of the form:
(state, symbol) -> (new_symbol, move, next_state)
move: -1 for left, +1 for right
"""
self.rules = rules
self.state = start_state
self.blank = blank
self.tape = {0: blank}
self.head = 0
self.steps = 0
def read(self):
return self.tape.get(self.head, self.blank)
def write(self, symbol):
self.tape[self.head] = symbol
def move(self, direction):
self.head += direction
def step(self):
symbol = self.read()
key = (self.state, symbol)
if key not in self.rules:
# No rule → halt
return False
new_symbol, direction, next_state = self.rules[key]
self.write(new_symbol)
self.move(direction)
self.state = next_state
self.steps += 1
return True
def run(self, max_steps=10_000_000):
while self.steps < max_steps:
if not self.step():
return True # halted
return False # exceeded max steps (likely non-halting)
In [7]:
rules = {
("A", 0): (1, +1, "B"),
("A", 1): (1, -1, "B"),
("B", 0): (1, -1, "A"),
("B", 1): (1, +1, "HALT")
}
tm = TuringMachine(rules)
halted = tm.run()
print("Halted:", halted)
print("Steps:", tm.steps)
print("Tape:", tm.tape)
Halted: True
Steps: 6
Tape: {0: 1, 1: 1, -1: 1, -2: 1}
今天花了一天来整理现实物品和数据资料，明天计划给项目的数据画森林图