python 解决八数码问题

2744557306

题目描述】
  M# r& o/ d" F" N
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
9 G, [6 Z1 \# r/ i; [( a0 _' b
1 X- g9 I4 l1 Q6 f; ^2 o0 ^例如：

1 2 3
  c+ ~( O/ P% w( c& I1 W7 Hx 4 6
- z. {% j2 y3 W, O: s" z7 5 8
1 e% u6 U* I7 ?0 c! a9 p) y  L        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
5 o, E9 y1 n- E0 J$ f, e4 5 6
; D# ~! E0 o1 \- h. z1 P7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3   1 2 3   1 2 3   1 2 3
. a; x/ E. \% H7 V9 ]: |/ Z3 n2 Vx 4 6   4 x 6   4 5 6   4 5 6
* F" k) u2 Z5 D7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

, P" s8 ]2 G3 ?& ?* l【输入格式】

, ]) s9 {) [5 z% P        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

9 O; I3 C! W! \1 2 3
" h& Z& X* I. ]5 q  x; Q( z8 {x 4 6
7 5 8
9 j/ X" H: s  D* [# o" C        则输入为：1 2 3 x 4 6 7 5 8
9 e4 W5 z- Z0 G5 \4 y4 \
【输出格式】

        输出占一行，包含一个整数，表示最少交换次数。
5 o* ^% v7 P' t
        如果不存在解决方案，则输出 −1。
' Q* X1 Y7 P1 g/ c- l8 ~
3 ~3 \$ t7 y9 D6 a6 H: h& L【输入样例】
% b9 j2 q5 I( S# c( `7 q; A) V& K
; L9 w4 z; C2 _" e, h2 @4 n- N2 3 4 1 5 x 7 6 8
6 a" H5 M. D, _& k【输出样例】

* v& v+ c2 L% R3 P% t19
* p9 ^7 Z5 f0 f【解题思路】

        简答题，用BFS遍历查找即可。
. S, K3 b0 P7 ]! \7 p
( b2 Y6 l4 y/ J% p【Python程序代码】

, Z5 p! q+ ?4 G% ~from collections import *
* Y6 Q+ G2 q6 s" v. L/ ~pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
dir = [1,-1,3,-3]
3 p/ e& j# o1 p0 t% w) x" p5 W' ~s = ['0'] + list(map(str,input().split()))
idx = s.index('x')
* L$ D' c( [! i4 w1 `mp = defaultdict(int)
def bfs():
    q = deque()
    step = 0
1 l- V2 `/ ]0 ?0 l* l) C  ~    q.append( [s,idx,step] )
' y7 _& R6 S2 E0 @" F' \" L    ns = "".join(s)
    mp[ns]=1
    flag,res = 0,-1
. T8 l. N" g6 W) j* x9 w    while q:
! Y  V% q: N5 y' N' b" T/ o4 C        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
/ i; A& N3 D9 Y% l9 a2 [- f) Y            res = step
            break
        for i in dir:
            teps = ss.copy()
            nidx = sidx + i
5 P$ o- m/ |. I% k! @2 J; U  i            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
% l" R+ {, t1 e' z- h7 T            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
' i. @& m# @) v7 O' `. C, c  J            nteps = "".join(teps)
1 q! Y- _4 n3 r9 ^            if  mp[nteps]:continue
            mp[nteps]=1
, G7 Z& J% P! C" V: O            q.append( [teps,nidx,step+1] )
    print(res)
: a+ O1 P( B4 V5 n; l. tbfs()

0 V( j8 k! U7 V2 j
2 u" G, i, c, r: w4 [# ~2 ~