python 解决八数码问题

2744557306

题目描述】
/ I- R9 S* |2 R( Z& i8 ^
/ c4 z4 H# p# F1 z        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。

例如：

1 2 3
( f9 @# F7 |  s" b# d* hx 4 6
( K# Z6 A1 V. \% E. {7 5 8
7 ?6 j& S5 R: o        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 q* ^$ s$ {( D- |) L$ V, R: I* K" M7 8 x
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
0 U; `% H) Z4 X
1 2 3   1 2 3   1 2 3   1 2 3
8 @6 E6 p, w% Kx 4 6   4 x 6   4 5 6   4 5 6
: E0 n" \- J+ M8 S! h3 g5 R7 5 8   7 5 8   7 x 8   7 8 x
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

【输入格式】

. n3 q$ h  g' f7 O# }% n, H6 C        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：

1 2 3
: ~: w* a9 G$ E9 X  D$ j( i  Ix 4 6
8 s! a! t: F8 e" j: j6 ]$ T7 5 8
" Z8 L, c$ a+ G: b        则输入为：1 2 3 x 4 6 7 5 8

【输出格式】
7 n7 z3 S* U8 d' Z
  z6 ~9 ]. F+ \, p        输出占一行，包含一个整数，表示最少交换次数。

        如果不存在解决方案，则输出 −1。

【输入样例】
, y7 @+ R. Y5 T  [; E
2 3 4 1 5 x 7 6 8
【输出样例】

& f* X$ w. S/ B" w$ {19
* }' N) C3 V1 E【解题思路】
) C! W8 g% O, T9 s5 v
- A! a$ B( D; V* Y" W        简答题，用BFS遍历查找即可。
5 w$ j2 \8 S; G/ [3 F, i
6 U0 x: K6 h: N【Python程序代码】
1 q0 D& \, H3 `! r; ?% ]
from collections import *
# h% j: |3 P6 v) _- apd = ['0','1','2','3','4','5','6','7','8','x']
norm = "".join(pd)
dir = [1,-1,3,-3]
9 Y; L3 w; B9 }7 u% G: ]2 r3 Vs = ['0'] + list(map(str,input().split()))
idx = s.index('x')
; v! b" i1 a$ ?. Y9 F  L9 \mp = defaultdict(int)
def bfs():
, K1 n3 {' h* C+ R7 L# A2 n$ ^6 w  H' Z    q = deque()
    step = 0
    q.append( [s,idx,step] )
8 H8 t& `( H/ c  g1 i    ns = "".join(s)
& H8 X7 B7 l, d# S    mp[ns]=1
4 n- K9 d( v% l3 A1 A* u    flag,res = 0,-1
    while q:
        ss,sidx,step = q.popleft()
: g$ A5 v/ b/ R9 C, K        if "".join(ss)==norm:
; I9 C1 u' V. u  M; A! ~: e2 U            res = step
            break
        for i in dir:
            teps = ss.copy()
$ h, K) c$ l' I: |3 K7 P$ D            nidx = sidx + i
' _; v$ g3 E, K/ w# T6 C- C            if nidx<1 or nidx>9:continue
            if (sidx==3 or sidx==6) and i==1:continue
9 K/ j! s3 w: }% h( q2 l4 m            if (sidx==4 or sidx==7) and i==-1:continue
7 Z$ x' J7 ~3 S" \$ S# S6 E            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
. e1 A+ o! M9 T: g7 X) q% \1 j. S            nteps = "".join(teps)
            if  mp[nteps]:continue
            mp[nteps]=1
, E7 J5 j- P9 I$ Q7 H            q.append( [teps,nidx,step+1] )
    print(res)
1 U& b: _1 S) Q5 G6 Ibfs()

6 V8 D# E; _+ s) ~- C

9 C, {- D; I4 @0 U