python 解决八数码问题

2744557306

题目描述】

        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
. Z7 y! o* d1 z, \9 ~3 L
例如：
* @4 B+ m) c) V! N  [6 x" V
1 2 3
. r0 V' c' Q; _- Y6 t9 M/ U- ~x 4 6
7 5 8
) X$ A& H# M. }+ ?9 Z5 L        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
% n: ~+ ^( {0 A8 U  w- k4 5 6
% q# \% B( O7 m3 Z+ b* g5 [* b7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下

1 2 3   1 2 3   1 2 3   1 2 3
0 \7 }6 R$ ~: @. m; Y; Px 4 6   4 x 6   4 5 6   4 5 6
6 x* Z% U4 o5 [7 O7 5 8   7 5 8   7 x 8   7 8 x
3 @" V& p8 u( R1 F         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

7 @0 v4 ^2 G) F1 h* Q3 p0 V( D) s% L5 x【输入格式】
& ?  t. K, o6 a, @
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
1 f5 v( a  W( E3 P# f/ w4 U5 }
1 2 3
* x! v7 b7 X/ ^$ O3 Ex 4 6
  a! f4 C* p$ p5 ?! x7 5 8
! Z: w5 J5 ?1 X3 R+ k: K# B        则输入为：1 2 3 x 4 6 7 5 8
$ H" q/ h# ?% t$ Z  e
【输出格式】
  d+ [5 a1 F' ?5 [# ?8 z1 ]$ X
        输出占一行，包含一个整数，表示最少交换次数。

        如果不存在解决方案，则输出 −1。
+ f% L1 l5 N  ]( ~  C( f3 b
9 F( y5 D. d  o& S2 X2 A【输入样例】
: s% `; J) N8 i
( i2 y, E/ q3 T: ]. s) ~& p2 3 4 1 5 x 7 6 8
【输出样例】

19
" |3 ~( H# e; \2 \" D【解题思路】

; C$ ?- F0 L* S' q" x& ~        简答题，用BFS遍历查找即可。
7 ~! P. m* ~& A
: |  ^1 H! [5 N+ D  q9 F) g' f* X+ R【Python程序代码】
9 p- `' x) d8 `
: j9 E' \% T; B7 |$ _( afrom collections import *
pd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
) V7 b+ Z' {8 c* F1 M; Rdir = [1,-1,3,-3]
* K8 b, a% ?' ~* P, Is = ['0'] + list(map(str,input().split()))
" ^4 v4 s5 w# }% }idx = s.index('x')
+ J6 T# O" g! y; Mmp = defaultdict(int)
def bfs():
8 V) H# P: Q. i* l  I  X4 h  Y( p    q = deque()
    step = 0
; C5 u6 z0 s" @  s! R9 U    q.append( [s,idx,step] )
    ns = "".join(s)
! P1 q& r8 R' z: p" k: d    mp[ns]=1
4 w+ X/ ]% B0 }% ~3 E! w5 D    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
        if "".join(ss)==norm:
            res = step
            break
        for i in dir:
            teps = ss.copy()
            nidx = sidx + i
2 Z# ]5 s( ]! ]! b4 z            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
  }$ w, H7 _$ U            if (sidx==4 or sidx==7) and i==-1:continue
: r* i- L3 @2 M, W            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
            nteps = "".join(teps)
            if  mp[nteps]:continue
: X% @, M3 I7 k5 j            mp[nteps]=1
            q.append( [teps,nidx,step+1] )
/ J& ~/ N$ K* e# b    print(res)
3 Q2 `, M7 _) r) e0 X2 ^bfs()
! T4 V/ o, W# j3 p& [
  j- W. u# A4 K$ `  V) h& ~7 U6 L
" }: l. q) p' H, B
7 U8 M0 z( c1 \; D

; b* c8 M) _: p# q% w