数学建模社区-数学中国
标题:
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 8
0 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; Q
7 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 e
1 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 6
1 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& n
7 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 f
norm = "".join(pd)
' b2 l7 Y8 `9 X1 k
dir = [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 o
mp = defaultdict(int)
j& l l5 X3 Q
def 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
2024-3-29 15:51 上传
点击文件名下载附件
下载积分: 体力 -2 点
2.23 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5