数学建模社区-数学中国

标题: python 解决八数码问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:44
标题: python 解决八数码问题
题目描述】
$ z' h4 i0 g% {7 C9 {7 A1 z! P* j  \$ m. t
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。$ o/ l9 r2 p7 Q9 L
! H8 B7 I1 }4 `4 ^$ s3 y
例如：: g  ?" m& K% T! S, X
- B' b1 k$ ~4 E7 i4 o; _# q. r) |
1 2 3  f' E2 C8 X+ ?' w
x 4 6/ p8 ?% f  Z/ G) V0 {& l& c7 d
7 5 80 R4 o  D1 a% i% q! ?' e5 N9 u7 O) S
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：  R3 e' D4 \: ~) W" u0 I
* p7 {9 ^4 @/ b. @) c, P
1 2 3/ I9 ^# f; U! p3 }( f8 }
4 5 6
; \; Y5 g" k- X7 a: p0 S; Q7 8 x* O7 `8 m9 i; X1 T# c1 f
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
4 ~8 w6 b- A7 R0 E2 {% m
) a9 D0 j8 `( _( h0 w0 s6 H$ ]2 ?  h8 e1 2 3   1 2 3   1 2 3   1 2 3* z' t$ y4 I& w' t( k
x 4 6   4 x 6   4 5 6   4 5 61 I% z; O9 g0 s
7 5 8   7 5 8   7 x 8   7 8 x/ O- c1 c1 ]1 l7 d
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。) x5 P0 b- o6 U$ m

: ^9 p  R. }. g! k4 X  `【输入格式】. Q* I/ c4 ^) p. E! p! o
" q0 z( ]4 S* k, D7 M
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：; Z, B0 P$ z$ s- e
. m2 s! ]  L( j
1 2 3 ! V& D5 s$ R5 a& v! w' Z2 n6 J
x 4 6
& ?) t: z5 O' t; Y8 P# X' j& n7 5 8 6 d$ ~& Y, _, C+ e7 n3 _
        则输入为：1 2 3 x 4 6 7 5 8+ F# N. d6 M7 q+ j5 o) E5 h  r
/ p0 z2 k0 [; n/ U6 U7 j: g" S5 g
【输出格式】4 E4 B: w: o* v) V7 @

* F: o" ]/ i& h        输出占一行，包含一个整数，表示最少交换次数。8 Y' v7 ~8 F! @3 v7 p
" E9 {6 W& U0 ]8 x
        如果不存在解决方案，则输出 −1。
( e( t. @' f8 f+ g
3 }+ |! w& P  E5 Y1 f! Z【输入样例】
" I8 S* M* S, d0 X# T0 b7 m# \, m# j; P' P# B$ P( q6 G# }5 l
2 3 4 1 5 x 7 6 8
; G- X+ Z8 b: ]【输出样例】) B+ `# N" S& e+ X( U8 B! A
& L' s# V2 Z' p
19
) d" @' z8 @" y3 u5 E5 C% F, B【解题思路】
: e1 @) O. b. A9 P, o
6 b: n+ r& C! g( }* ~: r2 w        简答题，用BFS遍历查找即可。
7 i- h- p9 h/ m. s5 C* Q" j; \3 `, b: x  r* b' ^- I
【Python程序代码】
4 t- S! D% N1 n$ |9 Q- @" F7 B  [" B' g. M
from collections import *
+ A! B' a1 q- _pd = ['0','1','2','3','4','5','6','7','8','x']
0 x' q1 D7 ^& J2 R  s9 fnorm = "".join(pd)
' b2 l7 Y8 `9 X1 kdir = [1,-1,3,-3]/ X. j. q% l- @6 \4 Z- ?* b" ~
s = ['0'] + list(map(str,input().split())), ^/ X+ d2 L) Y! h) ^/ C7 w
idx = s.index('x')
7 i5 a7 c4 j  omp = defaultdict(int)
  j& l  l5 X3 Qdef bfs():( t0 @" J+ V  `" b; ]4 s9 t
    q = deque()3 ]+ W7 U5 W% E+ d+ w, T
    step = 0
8 _1 I! Z' {( b2 u( b# ~% V    q.append( [s,idx,step] )
4 W8 {  F8 a/ J0 s' e) @. b    ns = "".join(s)4 s4 I2 |  n% o) y# E
    mp[ns]=1
  i9 m1 ]+ z: P1 y3 L    flag,res = 0,-1/ h* z+ D4 ^4 Y1 l
    while q:
$ {/ o& x; p3 p0 a        ss,sidx,step = q.popleft()
0 }+ K: `/ o/ ~% l2 p. H        if "".join(ss)==norm:
: |( d5 V6 V* g$ Z4 T3 o3 j4 j. x, v0 B            res = step
) _# u7 j3 F9 p% A; Z            break
5 [5 e1 \" J4 t! {: _+ G        for i in dir:" L6 O2 F. G$ W# U! s2 `& s
            teps = ss.copy()1 k4 P3 j% |. D8 @4 E" D5 j; x" m
            nidx = sidx + i
0 f% X: s) n: U$ C4 U            if nidx<1 or nidx>9:continue
, D  [& ~+ G  `( Z- K4 O( P; x            if (sidx==3 or sidx==6) and i==1:continue
% E# O$ J$ Y$ P2 v4 l9 e            if (sidx==4 or sidx==7) and i==-1:continue
( J/ x; X1 n6 x+ S            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
* W$ l/ u/ i9 m: s8 W/ r            nteps = "".join(teps)6 l% ^% M- O6 s& U
            if  mp[nteps]:continue
, V7 i+ R$ Y# ]2 ?/ G- K% p            mp[nteps]=1( {8 D, e6 \7 D* m# N" K, W
            q.append( [teps,nidx,step+1] ). d) D6 E+ I3 E( {
    print(res)
  i% r  r8 K3 k4 ~bfs()/ J' n# k1 o0 u+ d8 ^1 D

# x/ u& M4 E) n3 \* d+ e. X& X, t) w, ^/ ?; Z" Q

3 o8 _8 d' N* n/ z, U- C( {" O6 s, ]6 S) v/ P! p" q

8 q  E/ F6 ^. u/ ~0 P

代码.txt

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

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





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