python 解决八数码问题

2744557306

题目描述】
+ @3 t# Z# T$ Q- ?0 L
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

- e8 P. i' s7 K/ w+ f* }$ ?% r例如：
0 d" [- L4 S) I+ M. F$ ]
! R8 g4 t1 a+ E, C( R. n0 x1 2 3
/ Y/ k: T! {3 W! f8 hx 4 6
7 5 8
! b' V6 Q& D" T5 V7 J  l  s, O& G        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
; i2 F! l/ o7 f  r# @; O
5 }+ T9 Y: b) T% `2 O( M" N1 2 3
4 5 6
7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

) ^7 G3 F. h+ j. C% @' C/ p9 _1 2 3   1 2 3   1 2 3   1 2 3
- |! D9 v. o* W5 E  _' zx 4 6   4 x 6   4 5 6   4 5 6
3 m3 Q0 P0 Q. Z- @8 \7 5 8   7 5 8   7 x 8   7 8 x
; _* {- g! [0 G         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
8 u( [$ X' b  \
【输入格式】

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

. l3 {% l, U* }! H1 2 3
, ]5 x! r; b& Y: \& Wx 4 6
7 Y' h& ?3 B/ B: R% C8 m7 5 8
        则输入为：1 2 3 x 4 6 7 5 8

【输出格式】

        输出占一行，包含一个整数，表示最少交换次数。
% U' i% p$ L6 ?) i$ \2 v
        如果不存在解决方案，则输出 −1。

  F, x" }* c  D9 ~3 [6 W7 d【输入样例】
' |2 [8 {, Z, G( X
  I2 C; a" C3 Z1 a7 a- T6 ~2 3 4 1 5 x 7 6 8
5 r4 h" E: H9 c: q& Y  D, I0 @【输出样例】

8 f) l; @% B1 P: B* ^9 w19
5 ~& Q2 [, d' q' H【解题思路】
- D7 p! a. J; Q
        简答题，用BFS遍历查找即可。

5 g1 y% H" u, F& |# C8 \【Python程序代码】
& l4 k+ l: S" o$ }7 B
& W& U1 H$ h% ifrom collections import *
. e& y3 P- C6 ]) rpd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
' c5 N0 `3 M! O( w2 F  {* |$ Udir = [1,-1,3,-3]
2 M# |2 i( `7 w2 H" {s = ['0'] + list(map(str,input().split()))
3 B3 k; ~9 M+ E  k/ Lidx = s.index('x')
mp = defaultdict(int)
2 _5 h1 B  w5 s, F6 y& f% a5 r" @! Edef bfs():
    q = deque()
    step = 0
. o: s5 a1 B! w+ E: j% E) _6 k    q.append( [s,idx,step] )
    ns = "".join(s)
- U  P4 W( \: p6 K' }5 |    mp[ns]=1
    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
, C8 J$ ?2 [8 t  q* f  |# d        if "".join(ss)==norm:
# Z) T! w: A' v! c8 R3 W& L            res = step
& @% q  b  Q* L0 |2 t$ g            break
6 W- \2 y0 x) z, ?; E- g# A7 P0 _& b        for i in dir:
! g" |- W0 q! D* J3 u7 X            teps = ss.copy()
! S: ^" t5 l8 O            nidx = sidx + i
; a7 S; }1 j4 _, r' r            if nidx<1 or nidx>9:continue
- L1 C2 f7 ?) ~. E+ Y; V            if (sidx==3 or sidx==6) and i==1:continue
            if (sidx==4 or sidx==7) and i==-1:continue
% M4 Z* z6 r# t" S1 T  \            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
3 T; b8 M0 _# e            if  mp[nteps]:continue
            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
! I/ l8 |# L8 O' n$ J0 A    print(res)
bfs()



1 y+ p5 j3 f" S6 N+ j* D* _" x