python 解决八数码问题

2744557306

题目描述】

        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
+ S' T8 d" U" q. Z9 ~1 E
例如：
# l/ U& C1 Y+ ^8 R7 K; _
1 2 3
0 @3 u6 @$ k# p8 }x 4 6
7 5 8
+ D' b+ F" H" E4 }        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

4 T# n$ f7 n1 d9 {1 2 3
4 5 6
7 8 x
) z- W1 W* G, y( r        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
! _+ o, R. ^) W8 \7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
7 y# }5 {  Y. F% _) g* R: j. E1 q
【输入格式】
, m0 _! K, L- H* }
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
& t$ d9 y3 E- T. T# ^3 x: m# A9 L9 _# }
1 2 3
x 4 6
8 F$ J' J2 l  S  U3 a7 5 8
, i) F- R% [; m! b        则输入为：1 2 3 x 4 6 7 5 8

; p5 F  u% n- v3 `0 a【输出格式】
" z) ~% T/ b/ T( ]8 i6 N8 c
        输出占一行，包含一个整数，表示最少交换次数。

. V: u/ Q! _1 z# q" r$ B( q  a        如果不存在解决方案，则输出 −1。

【输入样例】

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

- T7 ?0 b8 x# k% R% `19
【解题思路】

        简答题，用BFS遍历查找即可。
4 c, q, [* G( G5 d0 Q
【Python程序代码】
9 l' B. V" s" S  q
+ K( l1 x3 @. }' ^8 A# lfrom collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
- R8 S" D6 @) I. Qdir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
8 j& }; V; ?& eidx = s.index('x')
* A# S+ w% r0 C9 |% c# o; lmp = defaultdict(int)
2 e; T. l% e- U7 ]def bfs():
1 w4 Q8 M3 _0 s: c2 }  [2 J    q = deque()
! x( i3 O, g* z6 U' \    step = 0
! q7 Z, p; u, h' F; T    q.append( [s,idx,step] )
" o, D  S. J3 r* O1 Z    ns = "".join(s)
    mp[ns]=1
    flag,res = 0,-1
$ D. t( @5 k* L$ m; ]4 f% A1 w( Y4 V    while q:
        ss,sidx,step = q.popleft()
/ t1 J" d  j5 A: p5 E& A        if "".join(ss)==norm:
) k& d" @* R% e) `1 v, k0 J            res = step
, j, K1 g$ b+ |' p2 K3 t4 A: V            break
        for i in dir:
            teps = ss.copy()
) q" m; D0 ~+ ]3 |$ o            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
& `; W' A% v% H1 o1 Y$ V            if (sidx==4 or sidx==7) and i==-1:continue
4 X' @* {, p/ R/ O& l            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
/ D, H! Z5 Q+ p: F- C            nteps = "".join(teps)
            if  mp[nteps]:continue
            mp[nteps]=1
2 Y! C/ ]" q; K+ b& C) K! I            q.append( [teps,nidx,step+1] )
4 V% q# K- h, n- N    print(res)
bfs()

) g6 B. y6 @9 t7 L


8 z9 j( M7 {+ P: ^5 [( E
3 u+ K6 p/ o- N1 X; l