python 解决八数码问题

2744557306

题目描述】
, f9 c% z7 P+ [0 Q; A
  S* g( d+ j5 D1 {+ x3 O6 p7 e        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

! x' W2 \0 ~# P# \5 V例如：
' z  X) Z# z" V6 |; M
" A1 p3 ]% r  @$ z0 }$ `7 d1 2 3
x 4 6
) l8 Q' W4 X1 a! j6 M7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

, r' R" X/ u" m6 p- H- ]1 2 3
4 5 6
7 8 x
: d8 \6 [& X; e( x# [$ E        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
$ }9 C: ]; F- I0 U
7 n! B- a& ]2 g9 D1 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。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

+ W1 Q1 \& h. V/ ?【输入格式】
. J  \7 S# N, |* e
- y2 M0 _( F& ^( C& A        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
" P4 N2 {% g/ H6 M/ K3 x
5 c1 o( s+ \* v6 ?+ B1 2 3
3 L* R, Y% q+ e8 [/ Nx 4 6
4 ~; N# v5 u+ \! f7 5 8
        则输入为：1 2 3 x 4 6 7 5 8
. j" B, c! U1 G, P+ f
【输出格式】
2 o7 ]  s- ^7 [, r0 a
        输出占一行，包含一个整数，表示最少交换次数。
  h' [2 A# R% t  g
        如果不存在解决方案，则输出 −1。
9 z- i! X$ X- D( P& x
" t# i" E8 H1 X1 _; k- U8 U) s: ^0 m6 v【输入样例】

) L8 ~& z% R' S/ J8 O2 3 4 1 5 x 7 6 8
( B8 A$ Z# {9 N7 E【输出样例】

19
【解题思路】
4 ]5 D  X, r0 t) q1 X
        简答题，用BFS遍历查找即可。

【Python程序代码】
' m+ m# m0 i2 Z) k& u* N( ^( G
from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
# q' c5 P( V2 @' P; ^norm = "".join(pd)
* Q* B  M& l. [. ]' t- tdir = [1,-1,3,-3]
( r7 g+ ?8 o9 b2 r8 ks = ['0'] + list(map(str,input().split()))
idx = s.index('x')
4 u' N3 S! M1 {, |5 Q) J2 z* r. Ump = defaultdict(int)
def bfs():
) C$ k4 u# h( B1 \7 I    q = deque()
    step = 0
    q.append( [s,idx,step] )
: f$ J6 j8 }" h: E4 R    ns = "".join(s)
    mp[ns]=1
* _7 d& B  ^+ `3 Y6 u    flag,res = 0,-1
& C- M5 I1 }+ g' M    while q:
6 B0 X8 ?0 F5 [        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
3 z* Q! E0 Y' b3 X            res = step
9 v1 B3 [) o' }' A& j# X            break
. t- I5 a; O* z' f' h3 K# z, A        for i in dir:
* |0 u" _, }) d            teps = ss.copy()
& u7 P. A, Z$ F: j            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)
            if  mp[nteps]:continue
            mp[nteps]=1
; d/ b9 m1 j: |- u! ^1 w            q.append( [teps,nidx,step+1] )
    print(res)
bfs()

& F8 A! W3 C, b  s; e" S

9 K5 K2 |$ P, L. G' f! y( A/ d2 a- a# O* t