python 解决八数码问题

2744557306

题目描述】
  T# w, U* O3 D+ o
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
) h& {+ {. H# q8 N
0 E; `) Y1 c6 @7 I例如：

1 2 3
1 F' g6 g' _/ o9 gx 4 6
" W8 h& m9 ?6 n" x7 5 8
1 V: h! S. Y; o) S3 `9 C! b1 H0 _        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

& K% N' w6 w  O* A1 2 3
, j1 t2 k* [1 |3 [- |4 5 6
7 8 x
3 M& W% \6 x+ w  A4 V3 `        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3   1 2 3   1 2 3   1 2 3
* Y$ R5 C, X# `x 4 6   4 x 6   4 5 6   4 5 6
2 [" J: ?. s1 x# p- O5 a) |7 5 8   7 5 8   7 x 8   7 8 x
# \+ L! S6 V. w/ G         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

【输入格式】
7 v0 e. P# S& D+ @
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
7 C4 B. G0 T: E  K4 _% j# F/ B$ q
1 2 3
' ^9 U' V4 l2 g/ m/ c: fx 4 6
7 5 8
) Z& M+ C4 W! w6 d) P        则输入为：1 2 3 x 4 6 7 5 8
) V+ h2 B/ N6 M; b- j2 \! a" k
1 K" ?; K) i  m% ]$ ?" ]  [4 A5 Z0 p【输出格式】

        输出占一行，包含一个整数，表示最少交换次数。

. t& Y2 z7 r. k8 N" W+ a+ o( ~        如果不存在解决方案，则输出 −1。
' B/ n) M$ p. `6 ~4 ^
( }7 f% P, ]- I) S【输入样例】

2 3 4 1 5 x 7 6 8
% K5 T& v6 s. ^! _. i  P【输出样例】
6 B# L, ]' Y8 N7 _5 K
19
4 }9 q; y/ T0 N. e) u【解题思路】

0 z3 F, B" l; s% l- M        简答题，用BFS遍历查找即可。
+ m$ u8 H" z3 P5 M" N. W
2 m/ C6 K& G% ~: g1 C8 h- ^【Python程序代码】

from collections import *
8 M9 T9 W1 q% Y+ o3 {; Cpd = ['0','1','2','3','4','5','6','7','8','x']
% i' [4 Y6 n, F' vnorm = "".join(pd)
dir = [1,-1,3,-3]
+ q- I- N4 \6 @4 S! T# zs = ['0'] + list(map(str,input().split()))
idx = s.index('x')
+ `. R; Y1 P+ B9 Q" U8 tmp = defaultdict(int)
5 ^4 y: L  h/ L" _3 E' q7 _def bfs():
% ?/ \( C7 _- H' F9 S7 _    q = deque()
! H+ [" X+ J) [$ B    step = 0
! f1 O, _0 G# K$ U9 ~    q.append( [s,idx,step] )
+ O2 a2 e# v/ G* x! Z# E! h) ]" J  i7 z$ q    ns = "".join(s)
0 u; t) `' k2 E  I: h    mp[ns]=1
& ]9 X4 W* u5 O2 k/ W" V    flag,res = 0,-1
( v; Z) Q( N, h$ J9 ^    while q:
        ss,sidx,step = q.popleft()
6 Y* T7 z+ C) x* W0 V, U! g; y+ B1 J9 c        if "".join(ss)==norm:
" y9 Y! u# ]1 r) ~            res = step
5 ~0 @' C3 \: y! R2 A, n            break
8 X* W! `$ Y  V; e% f5 h        for i in dir:
5 z0 `, x1 q9 s4 u: q            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]
4 B9 }6 Q1 |# e& j) s            nteps = "".join(teps)
; h+ Z# Q+ o& V8 t# E$ T            if  mp[nteps]:continue
% P; V+ y! @$ J- ?  o            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
" U8 n1 N* u/ i9 d7 w: W8 s% O    print(res)
; A: x3 C, {3 r' u4 Mbfs()

7 r, M8 M, u' x8 E7 v
7 I4 N5 R* T. Z' c/ M: E


% n$ Q! Y- `/ X0 t# f