python 解决八数码问题

2744557306

题目描述】

0 q& ^3 k; X) f9 E        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

9 I9 T! F  a; f8 f0 ]( D例如：

1 2 3
x 4 6
) Q; T5 x6 @0 ^0 m6 c2 y7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
. w7 n1 V0 }% e$ d5 X" w
1 2 3
- l4 C1 g  V) e% j9 w2 p0 t4 `" ]$ e4 5 6
7 8 x
0 C6 R- D: q2 y: Y4 `) {3 L        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3   1 2 3   1 2 3   1 2 3
+ o2 p0 i+ Q: K" ?  a& O  Lx 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x
' X$ j* g. C: K: P( Q" V* y: d) R         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

- u  ]! B, W4 D, Y: V【输入格式】
  u* x" L3 a; T  W) t, m: a4 t
8 |3 S1 W: L6 K3 s" O! c/ J$ ~" A        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

8 y) G" t9 K! |1 2 3
x 4 6
8 R" ]* o& m  ?- w( _4 |% e7 5 8
        则输入为：1 2 3 x 4 6 7 5 8
0 t1 l0 ]/ U9 g4 O, Y* }9 i
2 T# s8 R) a* G& K【输出格式】
7 `  t/ `' t# K5 L# C
  `: l9 y2 U+ I( h        输出占一行，包含一个整数，表示最少交换次数。
) E( M# r9 u" h
1 p- _; |& z- e, J3 A        如果不存在解决方案，则输出 −1。

* R# I# k" f, k8 T7 j【输入样例】
1 Q" d3 z, Y, w; i% W5 C
, U0 m, K7 b) I  B) S2 3 4 1 5 x 7 6 8
【输出样例】
0 e! z, Q& i$ i+ g5 _0 O
19
【解题思路】
! O4 t3 A2 V; v) }5 p2 e
        简答题，用BFS遍历查找即可。

【Python程序代码】
. [. L4 s6 L9 @: a- B( ^0 d
from collections import *
. o& x/ X5 t2 W; a5 A  r+ J  b: Bpd = ['0','1','2','3','4','5','6','7','8','x']
  o2 t; J8 X" @# s& ^% [norm = "".join(pd)
dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
" E# A% ]. U7 q, i$ Y8 Y  q4 n1 nidx = s.index('x')
mp = defaultdict(int)
; J, f! l6 G& _( z: q* A3 o0 Ydef bfs():
    q = deque()
, Q  e  r" q' T( j. Y# l% R    step = 0
! N) I& S( M. u. t    q.append( [s,idx,step] )
& J$ z  ~6 r  F0 ^    ns = "".join(s)
7 ?7 }; ?( x* N6 {- P5 U/ x    mp[ns]=1
    flag,res = 0,-1
  P3 t2 d  l6 `1 s& G( P    while q:
) S2 f  f# N- D0 S$ I  q        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
& H* Z8 R5 ^) p+ X# A4 U# F+ H  ~            res = step
            break
        for i in dir:
            teps = ss.copy()
            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
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
% _& x$ O( z/ o2 T4 a4 P            if  mp[nteps]:continue
            mp[nteps]=1
4 r  |# R* |+ I            q.append( [teps,nidx,step+1] )
; X8 M. S3 F9 D! }8 Z# `: q+ j7 D    print(res)
bfs()
& }$ O/ [$ O& b  d9 H  h  j
2 n' I5 \& H( ~5 f* Z& K



. d+ ~$ j  ^$ l