野蛮人智斗的自动求解（通过python程序）

好久没玩了，这一次重新下回来玩到了野蛮人智斗环节，突然想起以前玩的时候无聊用python写了个小程序求最小步数，运用了随机游走算法，想进一步优化的玩家自己看代码就行，不想看的记住以下几点：

1.根据自己遇到的图片修改 " ip1=[] "里的内容，例如遇到拼图为：

1 6 2

8 7 3

5 4 空

就输入 ip1=[1,6,2,8,7,3,5,4,9] ，拼图编号很容易看出来，空位定义为第9块拼图。

2.运行后结果输出在与代码同文件夹的"步数.txt"中；

3.初始定义max=30，如果步数.txt中显示最'该步数要求内未找到解，请提高步数上限或模拟次数'，就把max改成更大，100以内都可以，重新运行。显示'初始图像错误'或'无解'，就是ip1=[]输错了，重新检查一下。（确实存在无解的图像，但游戏里不会给出）

4.步数.txt中示例如下：

最少步数为：18

8-->9

7-->8

4-->7

5-->4

-------

这里的8，9不代表第几块拼图，而指拼图底盘上的位置，永远对应

1 2 3

4 5 6

7 8 9

8-->9 指把第八个位置上的拼图移到第九个位置上

4-->5 指把第四个位置的拼图移到第五个位置上

初始设定随机游走1000次，大概率得到最优解，在20次左右（除特别简单的图形）。

特点讲解完毕，代码如下自取：

# -*- coding: utf-8 -*-

"""

Created on Wed Dec 23 18:59:50 2020

@author: suhui

"""

import random

import copy

import pylab as pl

ip1=[1,6,2,8,7,3,5,4,9] #初始图像顺序

ip=ip1[:]

p=[]

max=30 #初始为运行步数上限 超过则不再需求 若最终结果为max+1则未解出 需增加max重新运算

s=1000 #模拟次数 越多得到的最终步数越小

mp=[]

e=9 #数字9代表空格位

max1=max

count=0

tpc=0

f = open('步数.txt','w')

for i in range(8):

tpc=0

for j in range(i+1):

if ip1[j]>ip1[i+1]:

tpc=tpc+1

elif ip1[j]==ip1[i+1]:

count=-1

break

if (count==(-1)):

break

else:

count=count+tpc;

tpc=0

if count==(-1):

print('初始图像错误')

f.write('初始图像错误')

elif (count%2)==1:

print('无解！')

f.write('无解！')

else:

a1=[]

d=[[1,3,0,0],[0,2,4,0],[1,5,0,0],[0,4,6,0],[1,3,5,7],[2,4,8,0],[3,7,0,0],[4,6,8,0],[5,7,0,0]]

for i in range(s):

p.clear()

for j in range(max):

for k in range(9):

if ip[k]==9:

if k==4:

c=3

elif ((k==0)or(k==2)or(k==6)or(k==8)):

c=1

else:

c=2

for n in range(10):

a=random.randint(0,c)

if ((ip[d[k][a]]!=(d[k][a]+1))&(e!=d[k][a])):

break

ip[k]=ip[d[k][a]]

ip[d[k][a]]=9

e=k

p.append(d[k][a])

p.append(k)

break

b=0

lp=len(p)

if (lp>=8):

if ((p[lp-3]==p[lp-2])&(p[lp-5]==p[lp-4])&(p[lp-7]==p[lp-6])&(p[lp-8]==p[lp-1])):

break;

for l in range(9):

if ip[l]!=(l+1):

b+=1

break

if b==0:

if j<max:

max=j

mp.clear()

mp=p[:]

break

for r in range(9):

ip[r]=ip1[r]

pl.rcParams['font.sans-serif'] = ['SimHei']#加入中文

pl.rcParams['axes.unicode_minus'] = False#加入中文

if (max+1)>=max1:

print('该步数要求内未找到解，请提高步数上限或模拟次数')

f.write('该步数要求内未找到解，请提高步数上限或模拟次数')

else:

print('最少步数为：'+str(max+1))

q=round(len(mp)/2)

f.write('最少步数为：'+str(max +1)+'\n')

for m in range(q):

f.write(str(mp[2*m]+1)+'-->'+str(mp[2*m+1]+1)+'\n')

f.close()

#结果为步数.txt 顺序为九宫格

以上代码结束。希望得到反馈，如果能够帮到大家就最好了。