python 解决八数码问题

2744557306

题目描述】

! Q: F# t  j8 _2 A        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
1 S$ }, O0 V4 y+ q: h1 P" h( v
( _6 i9 x9 {$ D! G2 i例如：

/ o1 Y$ }( h" W$ S0 v1 2 3
; _) ?  h8 Z! Y8 Z# R8 tx 4 6
7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
! P' Z9 F6 y3 [* W7 p' ~
' R& a0 O( K/ X3 d6 N1 2 3
( _* \' d- u& V1 S4 5 6
7 8 x
2 g5 b+ d& {8 {        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

/ i$ h3 h- Z8 X+ j$ r1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 ?# v% L8 z7 i) \$ e- E7 5 8   7 5 8   7 x 8   7 8 x
( y0 T8 B( K3 A3 T         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
/ l& ~0 {, D7 q, i$ Q1 m  h
【输入格式】

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

1 2 3
x 4 6
7 5 8
9 |& V& B$ z* X; h" L        则输入为：1 2 3 x 4 6 7 5 8
, w( V  S3 Y+ ~8 {
【输出格式】
8 w; G7 I! i6 h0 P% u
        输出占一行，包含一个整数，表示最少交换次数。
$ m" J+ t& x- K% J; T% V  H
        如果不存在解决方案，则输出 −1。
+ f6 d/ ?6 e& m; m
【输入样例】

2 3 4 1 5 x 7 6 8
; V/ e$ |8 Z; ^【输出样例】

19
【解题思路】

        简答题，用BFS遍历查找即可。
5 `; r+ \/ b: y% x) C5 R6 N
【Python程序代码】

from collections import *
0 M) @  J1 C9 C5 \' p3 L, Ipd = ['0','1','2','3','4','5','6','7','8','x']
. Q9 j2 I$ N0 ]; b) N! ~/ y; Nnorm = "".join(pd)
* A+ }3 N( z7 r( xdir = [1,-1,3,-3]
* Z5 h; a1 N( m6 o1 J- r) hs = ['0'] + list(map(str,input().split()))
idx = s.index('x')
mp = defaultdict(int)
% M; u2 h  b8 N  h/ [def bfs():
    q = deque()
    step = 0
+ K: \7 b/ I2 ]2 {6 R3 j* _1 d! o' f    q.append( [s,idx,step] )
    ns = "".join(s)
5 g% z5 X' `& f) R" x: N    mp[ns]=1
    flag,res = 0,-1
    while q:
) N/ W, V. x" h; t/ o- X4 U        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
            res = step
            break
        for i in dir:
            teps = ss.copy()
' o  {" a# S9 x+ u3 ~            nidx = sidx + i
$ O) e; n' S2 h/ C2 u% W5 G            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]
; X1 @( y8 p8 z/ W2 P  ]7 p6 v            nteps = "".join(teps)
            if  mp[nteps]:continue
            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
- W) c7 o! [: j- N8 E8 ~    print(res)
* \% c3 `# U  \: [' r  @( `# Tbfs()

7 C0 @3 t; H9 q8 n2 G0 ^

( n2 r# P4 |% \2 Q% a& P0 n) s

# w7 W% ]4 g* ~, P9 ?% S