python 解决八数码问题

2744557306

题目描述】

0 G) `* Z2 U+ ?' P9 ?6 B. @6 v7 n, x        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

* \/ u8 z0 s! L# T' P* F( h例如：

+ n9 I+ M! C6 a1 2 3
x 4 6
  B) t3 V/ V% n) H2 A: [6 F7 F. s7 5 8
6 O3 ~, Z9 m7 Q1 v0 V        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
/ s4 f7 g; O8 {) V6 G# ^. U
1 2 3
4 5 6
7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

9 R2 s" m1 g7 `2 o& R6 g: Y0 e1 2 3   1 2 3   1 2 3   1 2 3
0 C9 V; T% ~+ _4 d3 ?% M2 e: yx 4 6   4 x 6   4 5 6   4 5 6
8 X2 N0 f6 ?! a* U7 5 8   7 5 8   7 x 8   7 8 x
2 g) P+ \$ `" A3 @7 F8 o3 s  X         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
% p, ], V4 Y$ x. @! F
: o7 _8 o4 Q$ D/ {5 _【输入格式】

        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
3 k8 Q  m% p9 d. l$ q7 f
$ l3 v8 z5 J! X' O9 f1 2 3
x 4 6
+ a0 V6 e- C, z% i: y7 5 8
        则输入为：1 2 3 x 4 6 7 5 8

$ }4 [( ^. m" r5 t; ?+ R# T【输出格式】
% f) J) P, v: ]& A$ |3 G0 x
! w0 s* i& a( P- z/ N3 q/ u        输出占一行，包含一个整数，表示最少交换次数。
# H9 c8 G" w4 q& C+ J9 J7 Y" h6 W
        如果不存在解决方案，则输出 −1。

4 U2 b5 F3 x6 K* v, d) I. L! I3 h【输入样例】

9 a0 b8 T! s& v# V* s  c0 \  n: J2 3 4 1 5 x 7 6 8
【输出样例】

! I1 o8 b" V* y% Z* L19
: H0 S; N0 r6 w5 r) X9 ?) T【解题思路】
$ _1 K. N% V7 @) u: F3 J8 Q, R5 x
2 q" j( ~2 e- d4 w5 T8 `, l        简答题，用BFS遍历查找即可。
" X* ]: R  s' U8 [
/ w9 S7 s0 C4 z% V【Python程序代码】
  G  P* U3 Z0 v2 z% m  M( H9 X
9 Q: k4 C; p7 _; ifrom collections import *
* ]3 f9 s6 C) C1 H( i( e+ h% x+ Gpd = ['0','1','2','3','4','5','6','7','8','x']
* e' N2 |, \, A2 L4 fnorm = "".join(pd)
5 ]' E" R; S% b7 E7 Gdir = [1,-1,3,-3]
3 D+ k) o& l! is = ['0'] + list(map(str,input().split()))
idx = s.index('x')
mp = defaultdict(int)
def bfs():
) B( l2 H' ^8 M; t2 e    q = deque()
    step = 0
" [' r: v: e8 g! ~9 ]$ L    q.append( [s,idx,step] )
    ns = "".join(s)
% J9 n3 P8 u* o; {7 M; l    mp[ns]=1
    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
( p6 X! h; T2 r) O: J# ~1 @            res = step
            break
2 h- \4 R1 r4 {: i  O. M; K        for i in dir:
            teps = ss.copy()
            nidx = sidx + i
            if nidx<1 or nidx>9:continue
* O7 n. q! S8 R# k            if (sidx==3 or sidx==6) and i==1:continue
4 Y) p/ Q: k. _1 H6 F            if (sidx==4 or sidx==7) and i==-1:continue
& }9 g: @- e. ~5 w. S3 B            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
" S1 O$ m0 M8 |& i7 R: P- a            nteps = "".join(teps)
+ C& j5 L& z# [            if  mp[nteps]:continue
( x0 ?5 Y1 u- ^, h3 O2 W            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
    print(res)
; |0 h: Q4 o  L7 U& V; s- a7 jbfs()
. F8 p# n( M, d1 m/ w* T
( j" T! S; W+ C5 G; ~

% `% {7 C& u- ]( Z
! C9 \8 W; p8 n% }