python 解决八数码问题

2744557306

题目描述】

        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

% U! l2 O4 P5 {例如：
- ^& z0 m1 D0 A: n( _' Q, d/ ^
; R6 k2 x5 ?4 L4 g1 2 3
x 4 6
7 5 8
- c3 a6 ~) D  z% S$ W8 c8 w4 p( d        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
! Y! K- M9 U- I
% Z7 G! U4 g, u) K) Y/ _/ d) Q# x1 2 3
4 5 6
7 8 x
; R4 v# h6 h! _; e3 s        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3   1 2 3   1 2 3   1 2 3
# T; O8 P' g& T0 C& G( Ix 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x
6 D$ k/ _' G: r% |  C         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
& f& _2 V; P; ?3 K3 y. A$ O: H4 H2 L
1 X+ M" Q4 d& b8 r2 G1 D+ @; d( a【输入格式】
! U* ^2 I6 O% G$ r2 s
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
- m% H3 k1 V% a* y
1 2 3
- B. X( R# b7 K9 E: ^1 i" lx 4 6
7 5 8
' N* U1 D) C1 ^8 l* R) b        则输入为：1 2 3 x 4 6 7 5 8
# Z/ u5 H9 |% C, Q* E( Q
【输出格式】

6 ?: @) {. B1 `5 f$ Z( _        输出占一行，包含一个整数，表示最少交换次数。

        如果不存在解决方案，则输出 −1。
. m8 Z* J) \# D# E4 S
4 d0 |' k' Y; M- }【输入样例】
/ m/ J  j, G* q# Z" o6 @1 |
2 3 4 1 5 x 7 6 8
: W0 v: g% U8 z5 m9 @% s5 g【输出样例】
6 [, a6 \. x2 L" N3 Z
19
【解题思路】

        简答题，用BFS遍历查找即可。

【Python程序代码】

8 N4 B" ^; _% u, Q# pfrom collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
: X5 o; ]6 x- s% w' ?5 tnorm = "".join(pd)
, d; T- e( p, R9 I6 J  ~. }  ~dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
& j" _, F/ Z- R: P1 V' i$ s# |idx = s.index('x')
( Q% c( `" ~  Lmp = defaultdict(int)
: O6 Y3 Y1 R- m3 Y4 Qdef bfs():
) O" I8 e7 f% c& s& @- N) r9 e    q = deque()
    step = 0
) b! g0 C' G" B: X    q.append( [s,idx,step] )
* T; y% w8 v1 }    ns = "".join(s)
9 W3 s; I4 {: I    mp[ns]=1
    flag,res = 0,-1
) R. H6 l. L1 T    while q:
  c- r# c/ l  i        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
: y$ D. l& X( N2 b9 S$ L+ @            res = step
            break
        for i in dir:
4 N% m  J4 ~$ ]( {1 c            teps = ss.copy()
            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
6 K" J: {. \# W& H            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
2 o8 `  p% }5 l5 E' V& i! T/ _    print(res)
bfs()
* ^* ^$ h+ b( k0 E

- o  n( G6 c. Q' J) z8 X1 u# B
! `) }3 q% D1 u
- g+ o2 v# a. P! E