python 解决八数码问题

2744557306

题目描述】

        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
% [7 a8 k' c( ?, t
例如：
. g" |0 u' n! o  W8 Q
1 2 3
+ W( d; Y6 L+ U. T# d- [$ k' l9 |9 fx 4 6
7 5 8
. d$ Y1 a. p- c8 t0 J7 R        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
. Z: S3 v) P3 b# w& J% C7 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
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
  R$ ~4 U: c* t0 k7 w
: s6 G6 o* e, G, p$ T2 S9 C【输入格式】

8 X3 H0 v7 n6 d* ^        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
( I7 X4 f+ i0 _& F* Y
7 Q! K4 x' ]) C. _% i% v: M* ^1 2 3
x 4 6
7 5 8
        则输入为：1 2 3 x 4 6 7 5 8
8 N9 g) A# c- J7 A- j2 Y
【输出格式】

" ]7 e2 k! L' L* y& v; ~        输出占一行，包含一个整数，表示最少交换次数。
) t" K0 y) _& @
        如果不存在解决方案，则输出 −1。
" ^( D) C  ?- a
【输入样例】

2 3 4 1 5 x 7 6 8
, J2 f9 N8 y$ f* e$ r4 o* M【输出样例】

19
【解题思路】

! U+ z/ E- j" h4 S  }# |  K        简答题，用BFS遍历查找即可。

【Python程序代码】

8 M+ M7 |% @4 d; d7 efrom collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
" F( a' ~8 W# J. fnorm = "".join(pd)
dir = [1,-1,3,-3]
s = ['0'] + list(map(str,input().split()))
idx = s.index('x')
mp = defaultdict(int)
def bfs():
$ ]6 ~' v5 _; c8 K; b$ o    q = deque()
    step = 0
    q.append( [s,idx,step] )
    ns = "".join(s)
    mp[ns]=1
    flag,res = 0,-1
; o0 M' u' }. l    while q:
        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
            res = step
            break
        for i in dir:
/ D$ c2 J4 v! q( H5 k            teps = ss.copy()
            nidx = sidx + i
            if nidx<1 or nidx>9:continue
* Y0 ~8 {# I/ F/ ]            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]
            nteps = "".join(teps)
2 {, L  e- T' g$ a7 J; W            if  mp[nteps]:continue
  w% ]/ Z4 {- N) ]4 F            mp[nteps]=1
1 ^- Q- J$ J0 p7 ~! X& c- }) b5 t0 p            q.append( [teps,nidx,step+1] )
8 @1 A0 u1 g6 s5 s    print(res)
7 R- T; a+ r2 G9 d% u4 j% nbfs()

+ ~8 Y7 g' H+ V) ?

( p2 M5 Y. I4 C( M3 M
" y* k3 r& ^" x, L: S  \; Y2 W1 g( A
+ R+ x# \* n% v% {$ P, H5 I