数学建模社区-数学中国

标题: python 解决八数码问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:44
标题: python 解决八数码问题
题目描述】2 U0 [) t- E3 ?" ]

0 i$ z  E( C% ^2 V        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
' m: _2 K1 c- l$ y% |* b  \% e0 v# H$ c
例如：
5 v& @# F: a, _6 O) r& j# ]& M* r- n2 r' R# r( O! P
1 2 3
1 ]7 \+ l9 J/ W$ n; o8 bx 4 6
+ _4 u* b. ~8 B8 F7 5 8! j& a% Z* w( w- |( R
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
+ f" l, U) a$ k5 N9 p) k! _3 [7 D. |9 Z. A( r/ y
1 2 3
' s1 q. m. [1 M4 5 6
8 G0 |  o, w: Q7 8 x
8 w" {3 l  r+ q0 Z% Y        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
4 u& H" k: w- a# H& F% a9 |. M. q3 E' ?# e9 U6 n) t: u
1 2 3   1 2 3   1 2 3   1 2 3
' {. I8 k$ \1 Z3 q+ @9 {3 Q2 g6 Kx 4 6   4 x 6   4 5 6   4 5 6& B6 l+ A1 ]: z/ o: s3 @+ L& C5 [
7 5 8   7 5 8   7 x 8   7 8 x- r* `0 e+ ^* o; d3 D, u0 ^
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
! t" b3 N; v0 _. H4 n
# b( a, B/ B* }  U8 |7 r【输入格式】# `" I. o+ e  E9 S$ z
; f* ^5 ]$ p  d2 x* L, o4 Q0 {* S- M
        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：3 O  T5 g; p/ b* K5 W: ^" V" N) s
) F  D! l: X" }! o1 O9 \
1 2 3 ) ^1 q2 s' x8 z/ `- Z
x 4 6 + G0 k) J0 m# q4 N
7 5 8
5 B8 \" M( `# P, p/ D* A        则输入为：1 2 3 x 4 6 7 5 8
% P$ Q. x; ?" X1 v6 m# N* l$ n5 J: @, Q6 _* b! z
【输出格式】" ~. N$ t) ]+ N6 S* f1 z0 b( @& L
9 v- X" O1 c# k) E7 g8 y- G5 T
        输出占一行，包含一个整数，表示最少交换次数。2 G" c6 i2 N4 ]* @9 T' \

8 {+ i( c2 ]* U( m4 g, S        如果不存在解决方案，则输出 −1。
" l( u/ S" O/ f, G& A
8 a" k* E* }0 |9 r【输入样例】
% @7 H% p8 n, w" x. i8 [' F0 L7 \
& ^8 H+ y/ R( o) W1 |2 3 4 1 5 x 7 6 8. J+ r* G1 ]% W- Z0 T! r+ W, v
【输出样例】$ v- u, M' D' A1 W- s
& k( V) ?: Q* u! z8 [( @! W5 L
19
: x, Y" A+ T) U1 e2 S8 L! I% v0 b【解题思路】
7 ~1 t# P7 @+ y) v' v0 N# r5 R
9 d6 r, ^. k; G3 E        简答题，用BFS遍历查找即可。. o  E/ V$ B) H$ y
( t6 j% G3 n* X
【Python程序代码】
+ ]' C# ~" R; R& `6 {( m& L/ X1 X! {0 a5 q' r* r
from collections import *
2 w* Y/ n/ }+ F. ^4 g7 \pd = ['0','1','2','3','4','5','6','7','8','x']
' d4 j5 s% O4 Q( V9 l+ m; ]norm = "".join(pd)
" C) L# P+ a3 b; P2 n& a6 ]dir = [1,-1,3,-3]1 A. p: E7 S$ p% `: W/ u, Z; F0 @/ ^
s = ['0'] + list(map(str,input().split()))" {8 ?1 G0 `4 {* O, k* M+ q
idx = s.index('x')0 C& ]) j$ a& @$ ]
mp = defaultdict(int): O/ P$ q0 O! U) ^; p% A, O1 W( L
def bfs():/ l6 w3 s* q/ _* l
    q = deque()8 U" ]4 y) S+ ^: B/ f
    step = 0# g2 A& _! f1 j$ i. L% N5 M8 W- l2 Q
    q.append( [s,idx,step] )- ^1 m3 a- v  e7 }. }: \) A4 Z
    ns = "".join(s)
+ W4 `- F. i( J3 {% A8 A8 T    mp[ns]=1# j; l; K9 e. x: i8 G6 c  }' l6 D
    flag,res = 0,-1/ O2 b8 m& h2 y! y; j
    while q:
: I' k) f+ I; T        ss,sidx,step = q.popleft()
" ?# ?" }! e1 W% a        if "".join(ss)==norm:5 l. W/ c5 a* w* @' C
            res = step
. N. D: t. l  V! j3 m            break
. p8 s* v- \) Z! D* w2 ?        for i in dir:
& ~5 Q! n0 Q& P, E0 S            teps = ss.copy()
' Q$ }* ~5 q7 k+ `            nidx = sidx + i. `, D. W# s: F- ]
            if nidx<1 or nidx>9:continue$ b- T2 C0 V- A" |
            if (sidx==3 or sidx==6) and i==1:continue
+ a& |* M- c4 j& x1 k            if (sidx==4 or sidx==7) and i==-1:continue! W- `8 l! x7 c) R3 r0 s
            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]/ H9 t0 i0 o" P% A
            nteps = "".join(teps)
; N1 D: _% b* E            if  mp[nteps]:continue
; R6 q; K; ?/ A& _# C            mp[nteps]=1
$ g! G- y! f4 w. C2 C            q.append( [teps,nidx,step+1] )% u$ E, G8 }0 ?; i& ?4 v
    print(res)  G7 h4 l* `/ \$ a5 ^
bfs()2 i2 P0 i+ T. y( J* F3 ^
* E: K+ I' `8 O  T0 ]7 I
2 r; H' _5 D) y4 }

/ l+ V8 ~" p( j$ J* O  q3 k6 d9 ^5 p, d* i- m6 Y
5 `, y- |; [9 O7 N$ q" }$ R. H# N

代码.txt

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

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





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