python 解决八数码问题

[复制链接]

字体大小: 正常放大

2744557306

1198 主题	4 听众	2978 积分

该用户从未签到

电梯直达

1^#

发表于 2024-3-20 11:44 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

题目描述】

      在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：

1 2 3
x 4 6
7 5 8
      在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x
      例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
      把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

【输入格式】

      输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8
      则输入为：1 2 3 x 4 6 7 5 8

【输出格式】

      输出占一行，包含一个整数，表示最少交换次数。

      如果不存在解决方案，则输出 −1。

【输入样例】

2 3 4 1 5 x 7 6 8
【输出样例】

19
【解题思路】

      简答题，用BFS遍历查找即可。

【Python程序代码】

from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
idx = s.index('x')
mp = defaultdict(int)
def bfs():
q = deque()
step = 0
q.append( [s,idx,step] )
ns = "".join(s)
mp[ns]=1
flag,res = 0,-1
while q:
      ss,sidx,step = q.popleft()
      if "".join(ss)==norm:
         res = step
         break
      for i in dir:
         teps = ss.copy()
         nidx = sidx + i
         if nidx<1 or nidx>9:continue
         if (sidx==3 or sidx==6) and i==1:continue
         if (sidx==4 or sidx==7) and i==-1:continue
         teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
         nteps = "".join(teps)
         if  mp[nteps]:continue
         mp[nteps]=1
         q.append( [teps,nidx,step+1] )
print(res)
bfs()