数学建模社区-数学中国

标题: python 解决八数码问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:44
标题: python 解决八数码问题
题目描述】+ q" _6 t. D* v' K" S4 U

) A9 m. d1 \! C# J        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
& \+ N1 O$ l; u. m3 H2 E& _5 H+ Q: Y1 q( D8 _) a+ x
例如：- W5 Q, l1 R' @- m3 \
/ T; U9 Z3 O/ v8 e' h
1 2 37 U- }9 q; D* k
x 4 6
* L+ m7 t5 P3 s3 \  B1 U7 5 8- E9 ]7 l  E3 m* ^0 g) L: g
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：% f$ L6 ~. M; ?) D
  C6 e/ Y& L: ^, l+ v5 }& I
1 2 38 ^4 |/ A3 n, r) W% o0 R. F1 Q7 N
4 5 6
9 T) L$ R* H( y6 U& t7 8 x
5 M# q8 H& }& g4 I) K$ l+ t7 @- H! A        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下) N9 B. G/ G: c

" i& ]: P0 f1 l5 X2 I" \; d1 2 3   1 2 3   1 2 3   1 2 36 v/ X1 n$ t% f
x 4 6   4 x 6   4 5 6   4 5 6$ A! Q" E$ Z- i7 N9 b
7 5 8   7 5 8   7 x 8   7 8 x
% r# Y  G3 O4 V' e# ?         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。& \1 j7 w- J/ ^
; w- ~7 ~3 s0 Q$ `! p
【输入格式】: y/ H# Z4 h6 s% D' ]/ j: a/ y' ]1 j
; f+ J. ]; |0 W
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
9 j8 [9 z0 ]  a. K4 [" k  k4 \6 `0 W. B
1 2 3 3 s" M9 i* {) ~4 D0 w: C1 d; t
x 4 6
3 S5 v* N+ D0 ^" N% Z7 5 8 . o6 `* o) T$ t  z3 s! i: f
        则输入为：1 2 3 x 4 6 7 5 89 S2 Q3 u6 Y# z0 u) `4 c

$ @3 F! t6 r2 q6 `6 n" n* q【输出格式】# ?( z$ ^  X+ C0 ~
6 N  }; L; S) S/ X0 B% D
        输出占一行，包含一个整数，表示最少交换次数。: n1 t+ r/ n% ]
: s/ j' P+ S' c9 y
        如果不存在解决方案，则输出 −1。
$ R: I9 o6 @1 e7 d! x! _# \/ t% \! {$ O& G) D# O
【输入样例】
6 L( n, K) }* W5 e* d! p' F7 H' v( s. W  g  _, ?
2 3 4 1 5 x 7 6 8) m2 ^( A' V% b1 A6 o1 X
【输出样例】
0 @# ]/ Q* t/ m1 f# x) D; H
  [& s1 l  `5 x$ U19
7 S) k6 B1 p* Q+ H. c$ w( l) ^. [【解题思路】
! L; u8 s& ]9 y! R
4 r! P5 c: _3 _! s) K0 |0 Q: S        简答题，用BFS遍历查找即可。& {; D+ K/ h: \3 p- M7 f8 b

! P0 a/ K7 @4 S; g" y$ l【Python程序代码】! V& W$ w( ?- j" P3 v9 j. \
, ~9 @8 ~4 p* E" |4 b
from collections import *9 ^+ e6 t+ m6 `3 h
pd = ['0','1','2','3','4','5','6','7','8','x']
3 M, x* D; m  u7 C& Mnorm = "".join(pd)4 ^2 W4 Z0 K- x. T$ m
dir = [1,-1,3,-3]
0 [$ A' l6 o. f; c$ W2 m! ?; as = ['0'] + list(map(str,input().split()))0 C- K$ M" K( @: t9 |3 Q! d
idx = s.index('x')& s9 k" J" R. ~9 D; e
mp = defaultdict(int)1 F  D: j: q/ j9 l3 A5 ]
def bfs():
0 n5 B! t- s0 a7 M! U0 i( Q    q = deque()
! a0 ~+ r, W. r' G    step = 0
+ A1 n7 K. K  y, N5 {    q.append( [s,idx,step] )
, z8 \7 M6 ^2 X) S8 O  n    ns = "".join(s)
$ @  t% {% r5 |2 D% k8 X    mp[ns]=1
: m: `; ^; F, k2 S    flag,res = 0,-1/ C4 G4 v8 y1 V7 f8 M: e# I0 v
    while q:
& M4 ]- s) I5 G0 j        ss,sidx,step = q.popleft()
! w7 a4 R4 ?) s  H0 {        if "".join(ss)==norm:
  S( w' \; [- m* b. a2 }            res = step
9 b7 o; H/ d4 N) L- T            break* `! g. v& T7 k2 ^+ |
        for i in dir:
* p6 q  F7 W* U2 u% ^* D            teps = ss.copy()5 {/ L7 e$ x2 O  \$ u! ?  F- c
            nidx = sidx + i" V/ ~2 P7 F. _$ k! k6 P
            if nidx<1 or nidx>9:continue
) _0 c7 Y4 k+ ]$ N$ A  f3 F            if (sidx==3 or sidx==6) and i==1:continue% j; m8 F' ]7 |: G5 N8 ~
            if (sidx==4 or sidx==7) and i==-1:continue6 }2 O( h- J7 n' E6 ^, W! s) C
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
$ r- e5 S0 @$ C* ^& t* s            nteps = "".join(teps)
5 C5 W" ~& S, [. O            if  mp[nteps]:continue, N: K* O$ i2 L$ G1 W8 V
            mp[nteps]=1( d! Q: o' @, o; w' L. P: e( x
            q.append( [teps,nidx,step+1] )3 Q- t1 G9 o0 E; m+ y& e: I8 ~
    print(res)) q, C& t( f+ v' T7 O' Z
bfs()( E* Q( p2 F: p( v
- c1 d0 ?  p# f: h; n2 s
& d5 J1 b/ Z; r3 W( Q  y
: p, Z- M. H7 s( O

0 y# \! E3 c0 x; u' A: x! P- {$ Q- ?8 R/ t: k+ t# A4 P* A+ c

代码.txt

2.23 KB, 下载次数: 0, 下载积分: 体力 -2 点

售价: 2 点体力  [记录]  [购买]





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5