python 解决八数码问题

2744557306

题目描述】
8 s" U- \/ E) M. ]; x2 d9 b
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：
. G$ \8 n1 W) h+ D, s
4 A. E3 a2 e6 p  ~  y  O1 2 3
x 4 6
7 5 8
0 M& @! ^2 ]% J! O, Y- X1 L  S        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

2 a7 O) g& v$ v* A1 2 3
( O0 Q4 B0 h9 b* S4 5 6
* }2 w/ f; X4 ?0 v% U7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 n& h1 E0 ~" R3 y  b4 ]) [! K. R1 2 3   1 2 3   1 2 3   1 2 3
2 N- a2 T: c: Z& V$ S. I8 ^8 vx 4 6   4 x 6   4 5 6   4 5 6
9 _+ @! o0 v* O- R8 d$ g4 _# f4 B7 5 8   7 5 8   7 x 8   7 8 x
; y' n2 {, M! i  D& o         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
" O* H* ]8 G6 _
" Z+ i4 d7 }8 T9 J【输入格式】
/ l- v/ T0 }/ v0 C# y& ?" h# q
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3
; a! R" A1 n$ Ix 4 6
7 5 8
        则输入为：1 2 3 x 4 6 7 5 8

【输出格式】

5 S; P3 R. I3 Z  N) n. f! g8 P( O        输出占一行，包含一个整数，表示最少交换次数。
& C& t. W7 e2 u9 h2 }7 x' f
        如果不存在解决方案，则输出 −1。
: P  e1 m; i8 i. f
# [* `+ O% b3 p" [: u  L【输入样例】
! [. k2 ]/ g# W  V+ b& Y; W
2 3 4 1 5 x 7 6 8
" b: \4 C/ s' |/ C) F【输出样例】

19
7 U, a. p1 c* i6 u  d- Z: M+ \【解题思路】
( {' F+ }$ l! ]  R+ o! [
        简答题，用BFS遍历查找即可。

【Python程序代码】

from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
dir = [1,-1,3,-3]
" l' P4 D/ w1 K$ |" e* c6 H% _! s9 cs = ['0'] + list(map(str,input().split()))
- k+ N  J- z' C+ [& {idx = s.index('x')
mp = defaultdict(int)
+ v5 b  h9 |- G8 I/ e7 Z% hdef bfs():
1 L9 m) k9 j5 j& g4 |" G    q = deque()
+ y6 T( }) K  Z    step = 0
/ U& ^3 U  s) I* j' C: g7 w& |    q.append( [s,idx,step] )
    ns = "".join(s)
' q. T/ ~  T/ P" t* F    mp[ns]=1
9 Z3 I3 i# w5 n- ^- e* @    flag,res = 0,-1
* J) _, |1 Q0 |9 t+ \% k) u    while q:
6 I2 [6 E8 u) X9 z4 g( _4 A# l) B        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
            res = step
' b/ b+ A$ Y+ B            break
        for i in dir:
$ [' Y( n& J/ b4 D8 S            teps = ss.copy()
8 ^4 t% K' a: t) S6 s" h+ s            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
. Q% B+ T7 ?# C            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
& F: P: D* A0 b3 {7 v4 `0 g% i            if  mp[nteps]:continue
: y8 y8 \+ `2 L0 P! f6 z" ]. \2 w/ d            mp[nteps]=1
. P( k+ H1 |" W" y2 x# e2 D            q.append( [teps,nidx,step+1] )
    print(res)
bfs()

$ F  I- E  [/ V* O

# i5 k: J; H6 i4 v0 g5 e! N6 s