python 解决八数码问题

2744557306

题目描述】

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

# C2 D/ M( d! z% R) Q, M例如：

6 C; V' w  P1 \* ^% K7 M! I% P1 2 3
x 4 6
% p' U$ m5 P( V4 x3 k7 Y" z9 s7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
5 Z# ]$ x: B' a/ W* Q0 W7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 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
0 ^) o" ]0 C& i7 C. v         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

【输入格式】
, p- O. F6 w2 @; E
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
; d' r3 r# l* s; A( S
% p: s/ }% a, J, M1 2 3
, F  u+ H3 s1 }3 U% i4 P3 gx 4 6
# k+ w9 V* R) z- \7 w- L7 5 8
! b; P6 e' z6 i* }8 Q% Z        则输入为：1 2 3 x 4 6 7 5 8
% `, ]0 A; ?# i% F' ~% @- O
% P. `  S+ z( x# M+ s7 `" ^' `【输出格式】

        输出占一行，包含一个整数，表示最少交换次数。
' N6 O) h) D9 d# ?( i* r& K
        如果不存在解决方案，则输出 −1。

【输入样例】
2 {7 w! f1 m( {4 T4 j" _  l3 j
2 3 4 1 5 x 7 6 8
) \0 K) Y1 N8 U& @【输出样例】
. U( U: t$ P$ n, c7 c. z1 L7 o
19
0 |' A1 R/ S0 K) ]1 K* q【解题思路】

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

9 O0 c% N: S6 y, [% _【Python程序代码】

/ o2 T, @! \, q) C6 w: Nfrom collections import *
$ X6 }& g; c: H2 U3 D. jpd = ['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()))
9 e9 ~' E* @) h: }idx = s.index('x')
mp = defaultdict(int)
% m; v1 }5 I6 ?# J, v% V# P9 V3 `$ kdef bfs():
    q = deque()
    step = 0
0 N9 u2 l5 u) s3 \$ ^; ^$ |    q.append( [s,idx,step] )
    ns = "".join(s)
$ |9 X* O0 [1 Y7 K    mp[ns]=1
! t( ]# u5 {% Q2 ~  `6 e9 ]    flag,res = 0,-1
    while q:
2 G& _+ ]/ M9 C( ], P# ^        ss,sidx,step = q.popleft()
8 A5 f( |" ]' g" S+ ~* a3 ?        if "".join(ss)==norm:
            res = step
: E, A% D7 ]8 x( u; ^+ Q) y5 @- u            break
/ T5 a" F9 X: K/ x- O        for i in dir:
            teps = ss.copy()
* Y+ J* e. b4 f* \            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
- \& g' b' ~2 t            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
- `7 k+ a) M8 Z9 v2 I( _( B# n            nteps = "".join(teps)
+ `, ]4 G8 V! J' F. m            if  mp[nteps]:continue
# q" g! N1 E: e' k            mp[nteps]=1
/ B" f3 ~" x9 l* E" H# L            q.append( [teps,nidx,step+1] )
( o: F+ c0 J/ E8 y; x    print(res)
bfs()

  y( L' g/ K, I8 G/ c0 F: N. i
$ O# X/ e/ `5 j/ N
% t# V! B# _- ?9 n
' V5 ~; W+ s( c% U6 a7 C  [
& Z* z$ A# `( q. K& \+ ~$ l