python 解决八数码问题

2744557306

题目描述】
) Y2 x5 h+ k' p! ^. q
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：
( ]' d. E# t: S8 c! b! @6 Q
+ ~& |" q8 d; g0 P. L4 f' |5 \, c1 2 3
x 4 6
# ]! k) J( ^% T  ]* w7 J5 x* J% R4 K7 5 8
; S+ E2 o5 C3 |        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
  ^; V  s! d1 S+ G
* {% q1 Z: e+ w) o7 N+ v" l1 2 3
7 v. [) S: S* U0 x4 5 6
& S( @" m) z/ U8 k7 8 x
+ S# B- j$ j- M        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
3 y- Q# w, H& R5 T5 Q
1 2 3   1 2 3   1 2 3   1 2 3
( X/ Z0 v! H& z( s3 Wx 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。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

【输入格式】

4 F5 s. ^) U5 ^8 t/ U1 H        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
: a6 g# ?9 `0 V  N# Q) X
1 2 3
x 4 6
7 5 8
        则输入为：1 2 3 x 4 6 7 5 8
. [/ |4 A* X5 K! {0 _9 n% L
【输出格式】
* {1 ~! ~- @( O2 s' B2 t
        输出占一行，包含一个整数，表示最少交换次数。

        如果不存在解决方案，则输出 −1。

【输入样例】
( A% c4 n1 m, g1 w
2 3 4 1 5 x 7 6 8
【输出样例】
$ J+ o# ]3 I# A' [
19
【解题思路】
6 |4 C* U( R! g' D9 q2 n1 O, L
        简答题，用BFS遍历查找即可。

【Python程序代码】
: E  V: \, U( S" Y. x1 Z! G# m
from collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
idx = s.index('x')
mp = defaultdict(int)
def bfs():
( g) d( U3 T- G1 ^% ^+ v' @    q = deque()
- y0 B: g/ a/ t. k: f# M    step = 0
    q.append( [s,idx,step] )
% J2 A: P1 c8 \5 ]+ |3 W2 r    ns = "".join(s)
4 o' p( u: s* d' b    mp[ns]=1
    flag,res = 0,-1
5 X& Y" q; ]2 ]* V# n    while q:
        ss,sidx,step = q.popleft()
; ~* H  g* ?( A( g" ~        if "".join(ss)==norm:
            res = step
; C' n* d& L2 N4 t5 o! h            break
        for i in dir:
            teps = ss.copy()
  ]/ r+ R! {: N$ ]" j5 W            nidx = sidx + i
, b# T5 z% V6 ?5 O" c            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)
/ c! }/ X# n( n$ T& V- N  Q# r            if  mp[nteps]:continue
            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
% D! F( H& P9 r    print(res)
bfs()

! }3 P8 H! Y& S, I$ h
* `# q. A' P3 I# K1 `
8 D7 k, t7 S; {& s
; C8 A3 c% @" D' O