数学建模社区-数学中国

标题: python 解决八数码问题 [打印本页]
作者: 2744557306    时间: 2024-3-20 11:44
标题: python 解决八数码问题
题目描述】
$ y  U: w: S" G& T! R. N) u* k, ]- s" Q& S0 y
        在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3的网格中。
# L, B# z. f! a: D  H- I4 e
: s3 X& ^5 k: l; u( Y例如：
, u/ B8 K$ @0 k7 }  h( I/ T/ C2 O- Z
1 2 3
, v4 q- h& }4 f. ux 4 6
  W! C# l# A+ N! J4 @. Y' o" ?! V, M7 5 88 s; U2 y9 @1 N7 F4 Q4 P
        在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
4 }1 r& A% |9 `( T# l0 Q7 g) v
! |3 W5 S+ C! d& V# t0 k  q. U1 2 3: u- a6 d! }8 q5 H
4 5 6
2 I7 \4 O$ ~# r/ q! O: Y7 8 x' }+ w$ l* C+ k
        例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下
2 l7 m/ k7 W4 f% w% x5 Y5 W% {5 S6 b
; A% i: I2 A/ I7 @1 2 3   1 2 3   1 2 3   1 2 3
1 B2 s; \  J* Cx 4 6   4 x 6   4 5 6   4 5 6
' R0 p# }+ E4 Z5 J7 5 8   7 5 8   7 x 8   7 8 x5 |9 D1 p0 o! T( b
         把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
5 y( z+ t. {5 P9 o8 L  `) ^4 x, Q" |3 u6 ~6 b$ Z, b9 y8 c" b
【输入格式】; v2 u  {* t6 B* T6 C, d

! v4 x+ u6 L( \: E        输入占一行，将 3×3 的初始网格描绘出来。例如，如果初始网格如下所示：
+ |* ~* @; N; ]! j, J
3 h6 [( R" j0 M# n8 `+ G2 x+ @* t1 2 3 + u- T0 n4 i# b
x 4 6 . J) t5 c- a( h6 N% O$ H# l* m/ v
7 5 8
+ B  }( P0 E0 I/ h3 H1 o9 u/ l        则输入为：1 2 3 x 4 6 7 5 8
) M% c" A! i2 j! W2 h" h  ~7 Y' W6 j1 P
【输出格式】6 c1 b5 W+ {9 U' W6 w

6 B# o+ @2 {; L0 D: [9 l- m& b        输出占一行，包含一个整数，表示最少交换次数。, E6 F' v' D% T2 u

5 p& u4 _; {$ [/ [        如果不存在解决方案，则输出 −1。( Z( R4 [  d' d* A5 D0 H' j: V

9 W1 z$ d5 M8 [% I( F( @- _【输入样例】
8 l8 K2 Y8 W9 N: y9 P( d2 y; c4 s$ K! B/ ?9 G; `
2 3 4 1 5 x 7 6 8
% D2 {1 `% l1 r: }. O【输出样例】6 a$ w9 K4 {. z6 Z$ C& H* `( {

5 f' p; x2 }: C# Q1 E0 f: j8 |: a19
/ P: ^0 E! T/ ^- G( Q【解题思路】- R3 ~# \4 Q" J( J1 N# d

8 L( L1 m# Q. ]+ e( {! k. r        简答题，用BFS遍历查找即可。
' K  r. f; \) c! T" T2 `) I% S& y# t! K1 A
【Python程序代码】% X6 R: v$ Q, W9 ~6 u# p
0 G  }3 y; ^6 J# D  I
from collections import *! B, M% Y4 T# Z1 I
pd = ['0','1','2','3','4','5','6','7','8','x']
+ ?: G) Y5 U8 w0 Z, ?9 vnorm = "".join(pd), u9 e( |+ P+ T. y9 p! \
dir = [1,-1,3,-3]
% p3 ^  L0 M9 P% c. n8 x; rs = ['0'] + list(map(str,input().split()))9 R  q8 Z0 ^& F( |7 I! d1 @) m( `
idx = s.index('x')
3 z! F) o  I! mmp = defaultdict(int)1 o$ S, M6 |  ]1 d) {
def bfs():
  `+ M8 T$ Y, t% H( ?3 B* B7 @    q = deque()
; q( t: p2 d) c. j; F6 l4 k    step = 0& p* w$ w. u+ T: k/ C( h' B! P, y- w
    q.append( [s,idx,step] )# H( q2 f- p1 @2 {4 g& k
    ns = "".join(s)
" Z  \" v& S2 j/ R3 v    mp[ns]=1% T: O* I2 S& X$ s
    flag,res = 0,-1
1 j- S! r8 I$ x8 a8 _    while q:
1 y) |" Q3 N% ^2 Z8 C: O' ?        ss,sidx,step = q.popleft()9 j! `- i& t+ Z. N( ^
        if "".join(ss)==norm:
$ J" b$ ^( ~$ |            res = step& e$ a) h& q! y# J& N: g
            break3 q' M7 _$ W: |& ^9 ]6 C
        for i in dir:
& N. ^' Y4 @/ a+ L+ c' S! O            teps = ss.copy()
+ e' s4 ]) u  s( d  Y            nidx = sidx + i8 h* u* Y6 O. B& `
            if nidx<1 or nidx>9:continue) v0 E; @+ y* l9 W8 ?
            if (sidx==3 or sidx==6) and i==1:continue! [: C: F) e6 [6 H) g- N
            if (sidx==4 or sidx==7) and i==-1:continue
0 r. F' v5 W7 h" O/ A( j            teps[sidx],teps[nidx] = teps[nidx], teps[sidx]
0 o8 y& I* [! q- q- Q& X            nteps = "".join(teps)
; R$ }0 l* o9 ~4 \5 H: g0 D            if  mp[nteps]:continue
# W' C% s# |" m" q; ]# ^2 E, U, X% a            mp[nteps]=1
1 o+ x% s3 Y9 |3 z* S            q.append( [teps,nidx,step+1] )
+ W3 T2 U5 R( v9 P; V. z    print(res)
+ Y7 V" l0 w; d  \7 t+ r& x( kbfs()
* j, m* O; ?8 t. ]5 j0 |! B+ h
! I' [. e) k) r7 z
5 v% m3 c  `1 F; W8 j7 Z" s/ H3 ?( b& o
( m3 R7 j& G" Q5 P% j) {

$ e6 E3 L+ [: f. Q( E, q1 H: ~

代码.txt

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

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





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