python 解决八数码问题

2744557306

题目描述】

" `. }6 I" S/ _) d0 F+ S% T        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
, s! c9 V3 y0 N) g/ e* w
1 W9 M# o7 y, V$ X3 t例如：
- A4 [. E2 r+ O+ s$ ?
0 c1 o0 B$ k/ x7 C3 S. d1 2 3
8 Q& J  P' p- l' fx 4 6
7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

9 G: }; a' ]& y! R5 e8 @1 2 3
4 5 6
% e5 o) F4 W& z; n/ F  r& z7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
7 y: F8 H. v) {* h) _6 b- ?9 O
1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
. I4 G# ]) `& P/ @7 5 8   7 5 8   7 x 8   7 8 x
* s  g# S" E: P         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
  ]- ]/ r2 m& S$ C0 S. q
; h; \) p3 i+ O% l$ z【输入格式】
+ Y. l: @" Z* @- A% P# S2 |
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
' d  L, R3 p" D, V  d! @/ |
1 2 3
( D% e* A( i  w. z5 N+ xx 4 6
  Y5 w+ W; K. }7 q& j7 5 8
+ m; r$ Z) x- L3 T8 {; k/ g        则输入为：1 2 3 x 4 6 7 5 8
( V$ F" v$ Q4 U  t7 O5 [
# b+ Y' J2 y. W* _  K6 ~2 x8 L【输出格式】

# o8 n# ^2 Z4 O6 h        输出占一行，包含一个整数，表示最少交换次数。

        如果不存在解决方案，则输出 −1。
3 k9 D2 v6 }- L& B! s
' c0 e0 E8 a+ W3 Z2 {【输入样例】

6 I1 m% Y& ^( T8 ~2 3 4 1 5 x 7 6 8
【输出样例】

19
【解题思路】
! W' N4 B/ e, V" W2 z. ]7 }
% F; C8 Q6 z! b+ B5 b6 e) L2 i        简答题，用BFS遍历查找即可。
5 h$ Q% h  J6 k/ E8 @2 K9 q
【Python程序代码】

, O0 n) y: z7 q0 _3 [$ S5 b) u( c) sfrom collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
" t! {7 X0 ^& [" Y$ N' {0 tnorm = "".join(pd)
dir = [1,-1,3,-3]
' f6 z# q( L' r; zs = ['0'] + list(map(str,input().split()))
/ ~! a0 r! B/ z. x5 didx = s.index('x')
mp = defaultdict(int)
def bfs():
% \2 Q% Z7 f0 L    q = deque()
    step = 0
# a# m' o. ?( f* Z% Q1 t0 ?7 [1 i    q.append( [s,idx,step] )
    ns = "".join(s)
) W+ F- }5 w  ?% p: W. Q    mp[ns]=1
  z+ K/ w6 f. p$ e; e    flag,res = 0,-1
$ ?9 F3 \8 I' b4 B2 @    while q:
) I) s$ i* t. N        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
            res = step
" m7 T1 _9 e9 |) I1 J& C            break
" K* w" Y' ?6 E; N0 p        for i in dir:
/ p+ m5 w* i: s( X2 @            teps = ss.copy()
            nidx = sidx + i
            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
4 }# q' B: Z+ Y6 F3 C            if (sidx==4 or sidx==7) and i==-1:continue
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
  Y7 z# F+ G; P& L7 a+ z            nteps = "".join(teps)
5 B; P3 D$ u& a+ ?$ {; D; o            if  mp[nteps]:continue
            mp[nteps]=1
. |( d' ^$ d( y5 P$ q            q.append( [teps,nidx,step+1] )
    print(res)
bfs()
' D% p' z8 M, J7 V4 g0 `* E4 c& O' t7 ~
7 S4 C/ K! m, z3 d5 [( n6 {
& ~' i) j: q7 Z+ w6 \7 F2 |$ ?
* w) g' W) h  t7 }3 y
) g4 f2 N$ E8 Y. P