python 解决八数码问题

2744557306

题目描述】
, k" H7 h# d6 E- S4 \* ~' X
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
# Y  v! ?8 o% f( v! Q
例如：

5 \" P1 R" G9 q1 2 3
! H6 o6 h. i' t# e7 A' O9 Fx 4 6
" D) h! k! a( _8 Q7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
: e$ U) U( l" F( D4 5 6
' \( s) Q/ s! }+ T7 8 x
0 g7 ^  F2 z- a  J/ n& u) C+ w        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
3 y. P$ t/ f5 T
1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
% U. U( A5 e2 K: G, o+ ~- y' U. e) M7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

2 w7 Y7 U0 B: T' p; l/ z【输入格式】

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

1 @  ]5 Z% y, a9 S" y  n- A1 2 3
. w& J& a% l, c6 e! v, Z0 Kx 4 6
7 5 8
& g0 @3 o1 x  Z* w        则输入为：1 2 3 x 4 6 7 5 8
3 J; C! L, [3 p+ h! \# A
【输出格式】
8 Q# a  `6 d6 A6 }
- Y+ F0 g& [5 a+ V: B* j        输出占一行，包含一个整数，表示最少交换次数。

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

【输入样例】

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

# m/ [1 J9 K0 {& O# A19
2 }. f1 w% z3 d) l% R5 P' E【解题思路】

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

! m/ W, }% G& w【Python程序代码】

* _& U# O/ a8 J5 b/ `from collections import *
7 L/ \  q5 f6 \+ ?2 t) x$ g, Qpd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
6 f1 n7 M, S. r% V2 g1 t7 Ndir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
& m  Y% f- P1 bidx = s.index('x')
' |8 K+ e' L" ]2 v; W; tmp = defaultdict(int)
/ T! _, {* h3 c2 s* v; Y  i/ e9 hdef bfs():
    q = deque()
% F0 B8 m2 {0 \+ |8 u  p    step = 0
    q.append( [s,idx,step] )
( ]. b0 N+ J6 M" U  F+ s2 x    ns = "".join(s)
    mp[ns]=1
    flag,res = 0,-1
1 O7 w" a0 B# r* J/ G- N: M3 Y    while q:
        ss,sidx,step = q.popleft()
' w* E% G- P) I0 w        if "".join(ss)==norm:
1 u# q, {$ ^2 x9 B& Z5 n            res = step
            break
        for i in dir:
            teps = ss.copy()
4 n: y6 a/ }% J( O1 n0 j            nidx = sidx + i
            if nidx<1 or nidx>9:continue
3 [; c/ ]% @3 V) `            if (sidx==3 or sidx==6) and i==1:continue
6 L4 {% l" F4 M8 B, R' |9 C            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
- L3 N0 ?1 e7 ?* c& m            q.append( [teps,nidx,step+1] )
8 t$ E5 X, N1 Q: ^    print(res)
bfs()
0 H/ M9 D+ i% q' }$ n: ?


1 ]# U/ i% u# K' p% w7 p0 o% R

9 Z* |+ W' y, c9 X+ @# q* e$ M4 T( y7 W