【DigiKey“智造万物，快乐不停”创意大赛】MAIX BIT KIT上“九子贤棋”的核心逻辑
[复制链接]
正在调试“九子贤棋”的自动求解代码，发现有bug，修复后觉得有必要梳理一下规则的实现方法。这里贴一下lucky9starClass和调用求解方法的代码：
################################################################################
# lucky9starClass #
################################################################################
class lucky9starClass():
def __init__(self):
# 每条边上有哪些点
self.edges=( (0,3,6,8),(0,2,5,7),(1,2,3,4),(1,5,9,8),(4,6,9,7) )
# 点在哪条边上
self.point_in_edges=[list() for _ in range(10)]
for i,edge in enumerate(self.edges):
for j in edge:
self.point_in_edges[j].append(i)
#print(i,j,point_in_edges)
self.point_in_edges=tuple([ tuple(x) for x in self.point_in_edges])
# 每个点上是几号棋子（棋子1-10号）
self.pieces=list(range(1,10+1))
# 每个号的棋子在什么位置（0表示空棋子）
#self.positions=[[]]+list(range(10)) # dict([[0,None]]+[[x,x-1] for x in range(1,10+1)])
self.pieces,self.positions = self.init_pieces()
self.game_point_id,self.game_piece_id=0,0
self.game_state=0 # 0 游戏开始未持子；1持有一子
print("init-1")
# 初始化棋子
def init_pieces(self):
# 每个点上是几号棋子（棋子1-10号）
v_pieces=list(range(1,10+1))
# 每个号的棋子在什么位置（0表示空棋子）
v_positions=[[]]+list(range(10)) # dict([[0,None]]+[[x,x-1] for x in range(1,10+1)])
return (v_pieces,v_positions)
# 测试某个点上的棋子是否可以移动目标点
def test_move(self,v_pieces,v_positions,start_point,target_point):
# 找到公共边
#print('test_move:edges',edges,start_point,target_point)
for e in self.edges:
if start_point in e and target_point in e :
i=e.index(start_point)
j=e.index(target_point)
# 起点有子、目标空，中间只隔1子
if 0<=i<4 and 0<=j<4 and not v_pieces[target_point] and abs(i-j)==2 and v_pieces[e[(i+j)//2]]:
return e[(i+j)//2] # 返回需提子的点
return False
# 移走一颗棋子（可能因为要移动或是被跳过）
def piece_pickup(self,v_pieces,v_positions,the_point):
tmp_piece=v_pieces[the_point]
v_positions[tmp_piece]=-1 # 不在棋盘上
v_pieces[the_point]=0 # 此点无子
return tmp_piece # 返回棋子号
# 放下一颗棋子
def piece_putdown(self,v_pieces,v_positions,the_piece,the_point):
v_positions[the_piece]=the_point
v_pieces[the_point]=the_piece
# 移动一步
def move_point_to_point(self,v_pieces,v_positions,start_point,target_point):
i = self.test_move(v_pieces,v_positions,start_point,target_point)
if i:
p = self.piece_pickup(v_pieces,v_positions,start_point)
self.piece_putdown(v_pieces,v_positions,p,target_point)
return self.piece_pickup(v_pieces,v_positions,i)
return None
# 测试是否是开局状态（所有棋子都在）
def test_is_game_start(self,v_pieces,v_positions):
# 每一个位置上都有棋子
return min(v_pieces)>0
# 显示棋子位置
'''
1
2--3-4--5
6 7
/ a \
8 9
'''
def debug_out_pieces(self,v_pieces):
print("~~~ Pieces BEGIN ~~~")
print(" %d"%v_pieces[0])
print("%d--%d--%d--%d"%(v_pieces[1],v_pieces[2],v_pieces[3],v_pieces[4]))
print(" %d %d"%(v_pieces[5],v_pieces[6]))
print(" / %d \\"%v_pieces[9])
print("%d %d"%(v_pieces[7],v_pieces[8]))
print("~~~ Pieces END ~~~")
# 计算某个棋子可以移动的目标
def get_piece_targets(self,v_pieces,v_positions,piece):
print('get_piece_targets','-func-0')
targets=[] # 可行目标点
print('get_piece_targets','-func-1',piece,v_positions)
position_point=v_positions[piece] # 求棋子位置
# 对该位置对应的每一条边测试
print('get_piece_targets','-func-2',position_point,self.point_in_edges)
for edge_id in self.point_in_edges[position_point]:
print('get_piece_targets','-func-3',edge_id,self.edges)
edge=self.edges[edge_id]
print('get_piece_targets','-func-4',position_point,edge)
idx = edge.index(position_point) # 求棋子所在索引
# 对棋子2个方向隔一个的索引
print('get_piece_targets','-func-5',idx)
for tmp_idx in ( idx-2,idx+2):
# 如果该索引在合法范围内 且 目标点可以移动
if 0<=tmp_idx<4 and self.test_move(v_pieces,v_positions,position_point,edge[tmp_idx] ):
print('get_piece_targets','-func-6',tmp_idx,edge)
targets.append(edge[tmp_idx]) # 增加目标点
return targets
# 计算是否棋盘上剩余的所有棋子都不可移动
def test_all_piece_can_not_move(self,v_pieces,v_positions):
# 是否存在某个棋子可以移动的目标点数大于0
cnt=0
for p in v_pieces:
if p>0:
cnt = cnt + len(self.get_piece_targets(v_pieces,v_positions,p))
return 0==cnt
# 计算棋盘上剩余的棋子数
def count_exists_piece_num(self,v_pieces,v_positions):
return len([ 1 for p in v_pieces if p>0 ])
# random.shuffle
def random_shuffle(self,v_list_in=[]):
import random
v_list_out=[]
while len(v_list_in)>0:
i=random.randint(1,len(v_list_in))-1
v_list_out.append(v_list_in.pop(i))
return v_list_out
# 求解
def solution(self,v_pieces,v_positions,steps=[],depth=0):
import random
print('__solution _depth:=',depth)
if 10==self.count_exists_piece_num(v_pieces,v_positions):#刚开始
#print("刚开始")
for i_piece in (random.choice([1,2,5,8,9]),random.choice([3,4,6,7,10])):#(1,2):
new_pieces,new_positions,new_steps=v_pieces[::],v_positions[::],steps[::]
tmp_point = v_positions[i_piece]
self.piece_pickup(new_pieces,new_positions,tmp_point )
new_steps.append( (i_piece,tmp_point,tmp_point) )
result = self.solution(new_pieces,new_positions,new_steps,depth+1)
return result
elif self.test_all_piece_can_not_move(v_pieces,v_positions):#无子可动
#print("无子可动")
if 1==self.count_exists_piece_num(v_pieces,v_positions):#成功解开
print("成功解开",steps)
return steps
else:
#print("失败",v_pieces,v_positions,steps)
return False
else:
#print("求解中")
success_flag = False
tmp_list = list(range(1,10+1))
#random.shuffle(tmp_list)
tmp_list = self.random_shuffle( tmp_list )
for i_piece in tmp_list:
tmp_point = v_positions[i_piece]
if tmp_point>=0 :#还在棋盘上
tgts = self.get_piece_targets(v_pieces,v_positions,i_piece)
for target_point in tgts:
new_pieces,new_positions,new_steps=v_pieces[::],v_positions[::],steps[::]
self.move_point_to_point(new_pieces,new_positions,tmp_point,target_point)
new_steps.append( (i_piece,tmp_point,target_point) )
result = self.solution(new_pieces,new_positions,new_steps,depth+1)
if result:
success_flag = result
return success_flag # 如果没有注释本行，那么一旦找到一个解，就会返回
return success_flag
game = lucky9starClass()
tmp_pieces,tmp_positions=game.init_pieces()
r = game.solution(tmp_pieces,tmp_positions[::],[],0)
print(r)
大部分代码都有详细注释，解释下连夜搞好的solution方法：
1、如果棋盘上有10颗棋子，说明刚开始下棋，那么只要从10颗棋子里任意取走一颗就可以了。
2、如果棋盘上没有棋子可以移动，那么只要检查是已经解好了还是失败了就可以了。
3、剩下的就是正在游戏中的情况了。为了节约资源，用的是深度优先搜索，递归实现。就是依次选每一个能动的棋子走一步，再求解新的棋局。
|
提升卡
变色卡
千斤顶
1/8 
京公网安备 11010802033920号
Copyright © 2005-2025 EEWORLD.com.cn, Inc. All rights reserved
