python 解决八数码问题

2744557306

题目描述】
' Z, R! ?# T* D- [3 W/ J
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：
- D& t/ Y+ J; J
  e4 g* T0 |& ~" z2 X4 y1 2 3
3 I/ [' V; N4 x' G9 }# u2 Vx 4 6
7 5 8
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
6 `$ P( E$ `! K% \; V$ i
! _$ |& _0 {+ @) D  x1 2 3
$ `) j5 y$ a+ L  y. G2 D4 5 6
7 8 x
( C1 u1 u$ o/ ~, r6 m$ r        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
: c2 N+ M/ }7 X4 w# E# s- g
1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
0 y, A0 Y: a: V* x7 5 8   7 5 8   7 x 8   7 8 x
: K7 L4 L% N5 M% G         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

4 b/ F- x, ^1 A1 N% `1 A【输入格式】

        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
7 s4 _# N- v$ w7 b
# _; ^1 n# R- _1 2 3
* r& K# j& d& a: N7 f& Fx 4 6
7 5 8
+ X, n  I# _/ m" S( R/ R* S  M        则输入为：1 2 3 x 4 6 7 5 8
& k2 C% u1 M* P. u. b
4 W- Y$ P5 t; M( i6 O【输出格式】

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

. C% \% m2 ]) e5 v, T2 g, F        如果不存在解决方案，则输出 −1。

【输入样例】

# ^, l1 o0 P% O8 ~' `8 v2 3 4 1 5 x 7 6 8
3 ~* S( b3 q. c; W' u【输出样例】
& I0 f" b0 _1 T
+ V, M4 L2 N4 v" P- P; b19
【解题思路】

, @4 |* x% K7 P: d. ]        简答题，用BFS遍历查找即可。

【Python程序代码】

from collections import *
- _) Q; @3 A/ h7 Y3 c! o* O- hpd = ['0','1','2','3','4','5','6','7','8','x']
$ o8 v1 H3 p2 ~" e) `norm = "".join(pd)
! |0 O0 F4 I- f: Q$ Q1 S6 |dir = [1,-1,3,-3]
: e+ |0 @2 Q9 {# T; f) V% B; ?8 ns = ['0'] + list(map(str,input().split()))
/ s4 J; ^& [* y1 u1 Lidx = s.index('x')
mp = defaultdict(int)
def bfs():
    q = deque()
" T# h% @% }( [) U( X+ X    step = 0
    q.append( [s,idx,step] )
  M: l5 ~" @, Q- W- |    ns = "".join(s)
    mp[ns]=1
    flag,res = 0,-1
$ N& _2 U* K3 U$ _  d# g, W# z    while q:
        ss,sidx,step = q.popleft()
; @# P# N) c* l; u& g  b- J        if "".join(ss)==norm:
' n2 T) T8 Z+ d# Z  Q* ^9 Z            res = step
            break
6 _, a1 A+ G9 j5 l& a3 `        for i in dir:
& B$ [! u; s+ u) ^# v            teps = ss.copy()
            nidx = sidx + i
            if nidx<1 or nidx>9:continue
% g5 ]% V' g; B7 S) x! @            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]
( t, `* Z& V' V% k; J" {: {2 b  f            nteps = "".join(teps)
            if  mp[nteps]:continue
+ r3 f& ~; |# v8 c0 Y            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
+ j3 n' M$ ]+ n2 U    print(res)
% `) W) _7 T. G, y. y2 Y3 Zbfs()
1 R; o$ Q5 ?2 D  u9 F6 i
: E$ c, k( W! {3 p7 f1 {8 B/ l
. G' w! ?! ]; p. _- M


# n1 d# W# p# b, c