python 解决八数码问题

2744557306

题目描述】

        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：

9 ^, K4 P! s6 _, O! t1 2 3
' U- a' D2 E0 @1 A9 gx 4 6
7 5 8
  R! D9 A! j7 J1 Q  I9 K& A        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
2 R+ s- Y) H+ V7 R5 ?. U
1 2 3
4 5 6
/ Y3 z2 h# `- w: |2 \7 Z7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
( F8 c8 V7 r. y8 n3 Q, ?
1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

【输入格式】

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

1 2 3
, M  r7 d) S5 K" m8 V. J8 Kx 4 6
' Q) t( h/ h+ f: U: V7 5 8
        则输入为：1 2 3 x 4 6 7 5 8

【输出格式】
% F2 i% i# y. p1 k0 p& u
% M0 n/ H) |/ q  R0 C  i2 D. w        输出占一行，包含一个整数，表示最少交换次数。
: w5 v' E2 m. _6 k
; ^4 j# d* v% j        如果不存在解决方案，则输出 −1。

$ j) n! {* V- @% U6 L- @+ d【输入样例】

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

- F& |! }, `# ], s19
1 ?9 O1 V0 L( i【解题思路】
! L' Q7 o" e7 k2 W; g
: v+ U1 ?* V) p; J- R        简答题，用BFS遍历查找即可。
" `( S' a, G! k2 F$ e
【Python程序代码】

0 [2 w5 b( \0 z6 E: E9 a9 Tfrom collections import *
" `% I2 K8 p9 A+ _6 R2 {9 rpd = ['0','1','2','3','4','5','6','7','8','x']
! \% M0 r& |7 ynorm = "".join(pd)
dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
idx = s.index('x')
/ O# a* J0 X: ]4 w% u# o( E( Mmp = defaultdict(int)
$ Q0 k$ b! X3 E+ idef bfs():
    q = deque()
' U/ ?" x; y  Q; J8 k9 X    step = 0
    q.append( [s,idx,step] )
    ns = "".join(s)
; k$ i( i1 @. C9 Z; A7 S& C$ |( E" g    mp[ns]=1
    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
; S8 @3 W5 l1 Z% L        if "".join(ss)==norm:
            res = step
' f- ^9 V% `& |            break
        for i in dir:
( P. @* p/ l6 U% f) f/ ^5 q3 [5 X            teps = ss.copy()
6 U5 E. M7 C6 C. q  n$ A! ^            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
            if (sidx==4 or sidx==7) and i==-1:continue
- f! d* v) e! p+ r/ j% _" \            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
            if  mp[nteps]:continue
3 T' J, K! r8 R" v            mp[nteps]=1
. L: T( w- V4 R1 y) s5 }7 l4 O            q.append( [teps,nidx,step+1] )
" S+ @- k+ q4 C3 m    print(res)
bfs()

, G6 t. V) d! \% A
7 |5 @- r" T5 ]$ O: ]/ N
" p5 q# G5 R# {+ I2 y