python 解决八数码问题

2744557306

题目描述】

* v& M& g& E" i! V' h        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：

1 2 3
: f* v0 ?3 G% ax 4 6
7 5 8
; L. F) L$ c+ h' f: S% s        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
) h/ ^( h8 k3 V" Z; k% R' S
1 2 3
4 5 6
7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
1 B% u. r, h( Q9 [; p: ?
1 g: r2 _  N4 m1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
3 l; m: d' f5 Z% J& R  _7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
0 O3 [, T" M2 y5 p% ~! l
% I2 z8 D, S7 H- Z' ]【输入格式】

        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
) j8 ]2 ?) @5 Z  H% L- ^: o
1 2 3
/ {# O- G% e( u' q- |; u( [5 Ix 4 6
7 5 8
2 K; T( F' g7 m1 C4 }        则输入为：1 2 3 x 4 6 7 5 8
8 v3 g' z+ _; B' F
【输出格式】
" J0 V. |' N- I8 F! l! H8 q
        输出占一行，包含一个整数，表示最少交换次数。
* p6 \2 G, l' t
5 H! i# }8 @. l. j; K3 g        如果不存在解决方案，则输出 −1。

  O+ P/ P' D) p【输入样例】

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

19
【解题思路】
# v4 c1 ^1 R. x/ E. Z( m9 j
  [  P' J$ {* y) T2 J        简答题，用BFS遍历查找即可。
5 a1 C1 F+ m8 u+ `1 h6 X; q3 L: H. {
【Python程序代码】

8 A4 t' r5 @, h4 g% q0 c2 Pfrom collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
dir = [1,-1,3,-3]
8 I# e  \1 x* H9 ]! ~% D5 C0 Ps = ['0'] + list(map(str,input().split()))
6 J$ L, ?$ m! d: ]idx = s.index('x')
mp = defaultdict(int)
8 p) R3 j6 t6 ]def bfs():
4 D# f' K5 P# i5 a. g    q = deque()
    step = 0
6 k; B. P4 E3 n+ B- y    q.append( [s,idx,step] )
    ns = "".join(s)
' e# g) y& F+ n& H    mp[ns]=1
    flag,res = 0,-1
    while q:
5 _; `2 f: r( p% m        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
            res = step
            break
        for i in dir:
3 I+ ?' ?* l6 }/ v' b! Q: G            teps = ss.copy()
            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
9 s, H  @$ I2 i% A) f            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] )
2 w' W% S% ?8 ^: q  {    print(res)
1 v& l( {" h9 Rbfs()

5 v' ^  a8 f6 S! U7 a

" @; T! X  @) L2 k6 C3 o; X& V. `$ t