python 解决八数码问题

2744557306

题目描述】
2 b4 Q$ z% M* [" E  q7 c1 ~- V
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
7 m. E, @3 G5 D
例如：

1 2 3
$ Q( P2 q; {; Kx 4 6
" R3 p9 K8 j# E; J  z7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
" W( \2 Y  K/ k7 8 x
2 z& ?) B6 j6 L% n/ H        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
: ]( A1 M& O& w. ]
, x! q) M2 g8 G2 y, e0 H; e1 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。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
* I4 U- Z& }3 H
1 G& E# N+ C3 S. [+ g% j【输入格式】
# b$ H0 Y8 g9 e0 |# p6 a+ J, O
# U" `2 A5 z+ d/ f/ r! k' q        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
! Q9 I' J+ ?7 Y" |) o. u
8 i9 ^7 x6 }, p9 H7 g5 }1 }  u1 2 3
' O: @; @* D9 ^3 q0 f( Px 4 6
" L2 m6 {8 [' q4 Z4 A* w; C7 5 8
6 \6 [/ r% w; G5 ]5 i5 U9 l- D' i4 N        则输入为：1 2 3 x 4 6 7 5 8

( ]( e8 e( k# I4 Z【输出格式】
7 f, r5 H8 C4 T8 O
        输出占一行，包含一个整数，表示最少交换次数。

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

【输入样例】

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

19
9 q+ U6 j5 V/ M& U3 j; ~/ O【解题思路】
4 r# c6 e- z. C6 ^3 u
, q/ R2 d5 n+ C- Y        简答题，用BFS遍历查找即可。

) c8 X( s/ \0 ?【Python程序代码】

from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
# @8 d4 L8 @+ |: J7 \dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
1 n5 U3 }+ w" W! d" V7 L7 Sidx = s.index('x')
. S) v; }+ C. u  }mp = defaultdict(int)
def bfs():
+ x3 k) x* S5 R% q4 `$ [4 w9 Y    q = deque()
0 _: w# T" C5 N9 \4 M& ]* s- e3 H    step = 0
    q.append( [s,idx,step] )
    ns = "".join(s)
- B0 D8 m8 j% B; M    mp[ns]=1
% g9 y% K$ a/ e, \7 r+ v    flag,res = 0,-1
! J# n' v$ L  [    while q:
        ss,sidx,step = q.popleft()
* T9 p9 T% i/ |+ c7 @        if "".join(ss)==norm:
9 m2 l: s5 m. k7 g' S  ?            res = step
            break
        for i in dir:
+ G% z) _+ h+ `8 o            teps = ss.copy()
+ I" @2 s2 p9 i; s4 Y! |+ m2 j            nidx = sidx + i
            if nidx<1 or nidx>9:continue
& N+ C/ S# m, P8 a6 ?; c            if (sidx==3 or sidx==6) and i==1:continue
3 W+ f: q1 J4 ~0 ]7 k            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
0 a- N3 s1 E9 R: i1 r9 q            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
    print(res)
+ h& a# u4 ?6 A- I  n$ Z* g) p1 rbfs()

# @( M9 n$ @$ W
% C; h, @0 B6 g! ^- [9 p* K

1 _- ]8 }; d+ L1 \0 q' ^