数学建模社区-数学中国
标题:
python 解决八数码问题
[打印本页]
作者:
2744557306
时间:
2024-3-20 11:44
标题:
python 解决八数码问题
题目描述】
5 M; v8 o+ j: i9 P9 K) x
% [9 w" w; U/ F
在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
- U& X' z5 _9 L( E# _7 T
, Y( G7 Q( \# B: U2 J
例如：
/ u; {! O* g3 y2 X0 d( D# p
/ X7 u4 F" S& `4 ]' k
1 2 3
' N% @ l9 z' f' I! ~7 j _7 _
x 4 6
8 z+ Z& _* v) F
7 5 8
7 E! b. o) w3 Y5 M" Y8 e% G! ^+ Z( }
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
3 l# w$ c, J: ?) R) P; G
9 |6 R7 Q9 x) n. ~6 ]1 N2 c2 g" M
1 2 3
2 G# b* c9 x- j8 }
4 5 6
6 s& d/ k( S" v$ M& }
7 8 x
4 L' r. G! d8 s/ I
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
/ y& y) B! J. Y
- n- w7 a) t. U- ~( E
1 2 3 1 2 3 1 2 3 1 2 3
8 `; y8 q N7 Z& Z. `, F6 A' s
x 4 6 4 x 6 4 5 6 4 5 6
3 Q5 a+ A1 l9 z p
7 5 8 7 5 8 7 x 8 7 8 x
2 Z" x; y& i& G& M+ P( x; O$ o3 e- `; p
把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
, o8 l8 S3 Q, \ Q9 E3 g. X
: }) J- X; A& V2 f2 U9 o2 `
【输入格式】
1 y9 R6 f/ t) H- j# {
/ {+ T3 o, \3 G N- M& |& h
输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
" ~& e. c' m1 E7 _8 l% ^- _( Z$ _
# V" H1 W" ~, _6 e/ J+ }
1 2 3
( h$ Y0 o% _6 J6 v! }
x 4 6
% w5 T; v+ S/ e. T' ?
7 5 8
8 J" [( ?, g1 a
则输入为：1 2 3 x 4 6 7 5 8
) T0 x( p2 m3 H) ^9 R3 }. b/ ?( P6 U
7 [% V6 c9 m/ f& x ]9 X4 x& m
【输出格式】
7 N% u( j, q) ]) A( x- `
% X3 k, a7 W- ]4 T1 m8 s7 j
输出占一行，包含一个整数，表示最少交换次数。
8 N: J0 g; K" j+ Z, D
9 @3 b7 a8 u( O# I+ ~
如果不存在解决方案，则输出 −1。
. H( V/ g( |8 i8 z& o/ y! f
/ L# U# Q4 b5 b1 ~4 [1 _0 k' c1 ~
【输入样例】
+ m/ b, a- V- o
6 s0 [$ t. ~. Q! Q+ T9 |, A
2 3 4 1 5 x 7 6 8
f& t- ^1 P1 H M+ \. Q+ @
【输出样例】
/ g7 s! @8 i) D. J
$ y" p5 u% P4 ]3 Z0 C; r$ d7 P
19
. ?% V% x/ S& C2 }. C2 @- @: k
【解题思路】
/ U! O0 O" H7 p, S& l8 [1 C
, d8 v0 V$ n4 f& Z
简答题，用BFS遍历查找即可。
& Z7 D2 `! D6 R( ]! o2 a
D& V2 k* _2 K) M
【Python程序代码】
7 S" \& U! {4 L
. w: ]; l7 k. U4 W
from collections import *
, S+ ^5 I: U- d
pd = ['0','1','2','3','4','5','6','7','8','x']
; s' P4 P+ C9 a" U$ L/ p
norm = "".join(pd)
5 \& @& ]+ [$ b
dir = [1,-1,3,-3]
4 ]- {9 x2 c6 r: w$ q9 P: y
s = ['0'] + list(map(str,input().split()))
2 ^3 C4 x: C6 g2 F5 |$ K+ w: @/ U7 o
idx = s.index('x')
5 K. ]9 Y# T6 X4 d. b* p9 O
mp = defaultdict(int)
) o# W7 P2 P1 U: G7 a1 n
def bfs():
8 Q% p$ }- X" a }1 `0 n
q = deque()
5 o& ?5 g9 G' r, d: i
step = 0
5 o& d+ K" s! B1 d* S& g
q.append( [s,idx,step] )
6 j$ w7 ~9 K7 d- L/ ~
ns = "".join(s)
' c5 E; Q1 [: V5 g; N7 C) P
mp[ns]=1
& w5 S( K1 w* n: M- |. q
flag,res = 0,-1
$ P6 i( Q5 x/ U: G# y9 q4 \" C7 P
while q:
0 n4 B+ { @4 o6 E7 y
ss,sidx,step = q.popleft()
& c3 I7 `9 z* b
if "".join(ss)==norm:
; k; J+ J1 b3 N! }% a4 @
res = step
# {4 A* k0 G3 U& a6 [, u$ p
break
2 `8 ~ {" v. X; N9 f
for i in dir:
6 S$ y# l, C# F; ?7 g# q2 g! q
teps = ss.copy()
# v" K/ Y) S6 x! P: [. f
nidx = sidx + i
% U5 E6 `% f" ]3 [* I# U; n: ?
if nidx<1 or nidx>9:continue
8 d: b: O- g! a7 a
if (sidx==3 or sidx==6) and i==1:continue
( m! U1 ^/ q% q: d1 B( @: x! ?
if (sidx==4 or sidx==7) and i==-1:continue
! d8 W- S+ D/ z& Z8 n
teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
- ?% k/ |1 ~5 Y' L7 T+ B; h: g- L
nteps = "".join(teps)
" V# p1 @4 g" z4 N/ u2 M
if mp[nteps]:continue
8 c. |/ J+ f- F+ ~/ N/ c
mp[nteps]=1
# A+ B2 J5 ?% s2 K0 t" S# h
q.append( [teps,nidx,step+1] )
" @. h# m! G9 e
print(res)
( I1 Q, b8 B" ]- d
bfs()
) I: h% T- g$ J( H3 ^1 U
' Q) V9 D n3 P" S
! b7 x' o* D/ h7 m4 d" [
% e0 T' U( U+ U7 N) I Z% E# q+ F
* M7 P) R A% N- P( d! Q9 B7 D
" h5 m$ g, Y' l6 Q. M' L$ J: R) h
代码.txt
2024-3-29 15:51 上传
点击文件名下载附件
下载积分: 体力 -2 点
2.23 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
