当前位置：首页 > news >正文

用Python写一个蜘蛛纸牌求解器：状态建模、DFS回溯与启发式剪枝的完整实现

news 2026/6/18 0:40:20

写在前面

本文实现一个蜘蛛纸牌（Spider Solitaire）的自动求解器，可以求解一花色和二花色的牌局。四花色由于NP完全级别的复杂度，纯DFS无法在合理时间内求解，但框架是一样的——换一个更强的启发式就能覆盖。

第一步：状态建模

蜘蛛纸牌的核心数据结构是10个列（tableau），每列是一个列表。还需要一个发牌堆（stock）。

fromdataclassesimportdataclassfromenumimportEnumclassSuit(Enum):SPADE=0HEART=1CLUB=2DIAMOND=3@dataclassclassCard:suit:Suit rank:int# 1=A, 13=Kface_up:bool=True@dataclassclassGameState:tableau:list# list[list[Card]], 10列stock:list# 待发牌堆, 每批10张completed:int# 已完成序列数

关键设计决策：每列中只有末尾的连续face_up牌才是"可移动段"。一花色模式下任何递减序列都可整体移动；四花色模式下只有同花色递减序列可整体移动。

defget_movable_segment(column:list)->list:"""返回每列末尾可整体移动的牌段"""ifnotcolumn:return[]# 从末尾往前找连续的face_up递减序列segment=[]foriinrange(len(column)-1,-1,-1):ifnotcolumn[i].face_up:breakifnotsegment:segment.append(column[i])elif(column[i].rank==segment[-1].rank+1andcolumn[i].suit==segment[-1].suit):# 同花递减segment.append(column[i])else:breaksegment.reverse()returnsegment

第二步：合法移动生成

defgenerate_moves(state:GameState)->list:moves=[]tableau=state.tableauforsrc_colinrange(10):segment=get_movable_segment(tableau[src_col])ifnotsegment:continuesrc_card=segment[0]# 段顶部牌fordst_colinrange(10):ifsrc_col==dst_col:continuedst=tableau[dst_col]# 空的列可以接任意牌ifnotdst:moves.append(('move',src_col,dst_col,len(segment)))# 非空列：目标列顶牌必须比源段顶牌大1elifdst[-1].face_upanddst[-1].rank==src_card.rank+1:moves.append(('move',src_col,dst_col,len(segment)))# 发牌操作ifstate.stock:# 前提：所有列非空ifall(len(col)>0forcolintableau):moves.append(('deal',))returnmoves

第三步：DFS回溯核心

defsolve(state:GameState,max_depth:int=500,visited:set=None,path:list=None)->list|None:ifvisitedisNone:visited=set()ifpathisNone:path=[]# 终止条件：8个同花序列完成ifstate.completed==8:returnpathiflen(path)>=max_depth:returnNone# 状态哈希去重state_hash=hash_state(state)ifstate_hashinvisited:returnNonevisited.add(state_hash)moves=generate_moves(state)# 启发式排序：优先移动能翻开暗牌的moves.sort(key=lambdam:move_heuristic(state,m),reverse=True)formoveinmoves:new_state=apply_move(state,move)result=solve(new_state,max_depth,visited,path+[move])ifresultisnotNone:returnresultreturnNone

第四步：状态哈希与剪枝

defhash_state(state:GameState)->int:"""简单的Zobrist-style哈希"""h=0forcol_idx,colinenumerate(state.tableau):forcard_idx,cardinenumerate(col):ifcard.face_up:# 编码: 列索引 + 牌索引 + 花色 + 数值h^=ZOBRIST_TABLE[col_idx][card_idx][card.suit.value][card.rank]returnhdefmove_heuristic(state:GameState,move:tuple)->float:"""启发式评分: 越高越优先"""score=0.0ifmove[0]=='move':src_col=move[1]# 加分: 移动后会翻开一张暗牌tableau=state.tableau seg=get_movable_segment(tableau[src_col])iflen(tableau[src_col])>len(seg):ifnottableau[src_col][-len(seg)-1].face_up:score+=10.0# 高权重# 加分: 移动后产生空列iflen(tableau[src_col])==len(seg):score+=20.0# 最高权重# 减分: 混色叠放dst_col=move[2]iftableau[dst_col]andtableau[dst_col][-1].suit!=tableau[src_col][-len(seg)].suit:score-=5.0returnscore

第五步：运行测试

# 一花色随机局面求解state=generate_random_state(num_suits=1)solution=solve(state,max_depth=500)ifsolution:print(f"找到解，共{len(solution)}步:")fori,moveinenumerate(solution):print(f"{i+1}.{move}")else:print("未找到解，尝试增加max_depth或换启发式")