python 解决八数码问题

2744557306

题目描述】

        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
- ~$ U/ d$ _; l/ ~3 {( l$ u$ S  N. n
" y0 S  H% l! x( H2 d# X, g例如：

1 2 3
% S+ O) n, B+ v+ B/ p# |+ rx 4 6
7 5 8
2 R7 e- N( o+ E+ n+ O3 E, b' [        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

" S: N/ M/ f7 A( v1 2 3
4 5 6
7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
- |  K$ Q) o4 O
* z7 z& L2 |0 c0 b; s1 2 3   1 2 3   1 2 3   1 2 3
6 J$ d! s- G* @x 4 6   4 x 6   4 5 6   4 5 6
: X" N% D$ R& g9 i, g- l  {7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
, h& V7 W. t7 r& X7 X
【输入格式】

, x* J# l. u+ M2 E4 j# T/ t        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3
x 4 6
% R8 p' D! Y6 z3 A7 5 8
        则输入为：1 2 3 x 4 6 7 5 8

【输出格式】
0 A8 J9 n9 l  e, R
8 k6 c$ X! F4 n# z9 z        输出占一行，包含一个整数，表示最少交换次数。
* G" o. |8 `0 C& n4 w
, c# \7 p+ q" m0 ~3 ]9 \* b- n        如果不存在解决方案，则输出 −1。
* x7 \# F' m* p0 ^3 Y" D. z
2 Y8 s$ {; W1 a1 Z' ^( t* [【输入样例】

* ~9 I# z8 ^7 O8 c3 P  L; _2 3 4 1 5 x 7 6 8
; s! d% V: Q( ^. b【输出样例】

6 n7 a4 D1 b' H- V0 P" v19
【解题思路】
) O' m. p8 O8 F# F4 A# r3 b% U
        简答题，用BFS遍历查找即可。
  I  Z: ]& P: k  K0 V, @  ^
. K4 ^+ k, |+ S, w+ d! x/ Z【Python程序代码】
0 S. C' X$ H1 Z
from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
# n- q6 b7 @  p5 {# xnorm = "".join(pd)
dir = [1,-1,3,-3]
( G5 V/ Q  n6 v3 q9 \, ys = ['0'] + list(map(str,input().split()))
idx = s.index('x')
( H8 P1 }! Q: r3 N1 Q4 R* S% ~! z& ymp = defaultdict(int)
def bfs():
    q = deque()
    step = 0
6 r# i, a4 ?3 `7 ~& y; f- z0 k    q.append( [s,idx,step] )
    ns = "".join(s)
( c- o$ p1 Q( P    mp[ns]=1
    flag,res = 0,-1
  c" G" q& V0 _- c; A7 q. O    while q:
        ss,sidx,step = q.popleft()
1 k' Q5 {5 U0 J/ y! U  g' I: H        if "".join(ss)==norm:
4 E+ `, w6 I1 G) \            res = step
# z/ m" t1 U- W: z1 B2 A            break
7 D  i+ A6 ~5 B7 i        for i in dir:
; l4 o! S, s0 m) G9 |! ]9 a5 }/ w            teps = ss.copy()
. A& |. O. ?, W2 A9 Q, V            nidx = sidx + i
: H/ A/ s8 m, O            if nidx<1 or nidx>9:continue
! f+ w4 }& M7 d, D            if (sidx==3 or sidx==6) and i==1:continue
            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
, D& s! ]# R4 R            nteps = "".join(teps)
            if  mp[nteps]:continue
! o7 x+ v# g5 F: ?! k9 H            mp[nteps]=1
% h* y, P# X3 P+ @9 l6 j            q.append( [teps,nidx,step+1] )
    print(res)
" T% t! @% R( H: |bfs()
" C# k/ i( Y, h
& M$ n0 X) L$ E
! u" d% y( w9 d
" A6 r9 e. x  @# w2 x; ?