数学建模社区-数学中国
标题: [灌水]喜欢迎接挑战的请进来！ [打印本页]
作者: god 时间: 2005-3-30 23:40
标题: [灌水]喜欢迎接挑战的请进来！
喜欢迎接挑战的请进来！ - j0 @0 Q7 V; M# I' O7 g
《小擂台》 " W* s5 Y. N1 J- n& F' X
这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所 8 f& }; I$ R! n5 Z
以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于
% i$ J3 r" @3 g: X- t/ E我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 2 Y1 C- P# U) D1 R! H U$ u
余生活，何况这个题目在今天研究，已经具有双重的考验作用了。
9 N, F( @ c( R/ v @) U 不要去找现成的答案。也不是那么好找。
! |% X+ M2 v, X0 i 一是完全用我们的大脑来解决问题，这个难度是有相当档次的。
" B& L7 T+ [" K: h4 W 二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出
Y8 N6 u8 Y5 `( ^% [+ B一个解决问题的搜索程序，解决这个问题。 8 W* w# n* H5 Y0 ~: I2 D0 S$ A
; Z7 t9 a F5 e0 h
1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重
' |# e+ _+ t# |3 h5 y8 I排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下：
) c( d- `4 g$ u2 x5 J3 N在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格 1 |- {: U9 A- r2 f+ Q
开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空 . k& _: q( T+ D1 K M9 y0 \3 B9 S
格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任 : b* {1 r' u8 {
意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、
2 e+ G: ]% C9 N9 O( l) G6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 9 h9 Z7 O/ k$ r: A- {. K
为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步 ' ~5 o# l# c0 B/ E& {& H. l
以内完成就是智商很高的体现了。 " j+ p) T9 t0 \) k7 K4 Z
2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 1 D; o1 t8 k6 a
但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 & E9 i, B8 I. }- m# J$ C3 N
事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段
8 Q3 l2 c; ^$ t0 ]! Z3 `4 Y——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小
3 r( C+ e! g# B时的计算机运算时间，才找到了全部的最优解。
# H1 Z! x% C0 q$ W7 A 他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能
6 X; @% j! m) Y" s完成的。
. B# X; O, g$ V 事实上，在20多年前当这个题目在国内公布之后，在短短的半年内， & n3 [; R' ] e7 q) J6 e) k/ e7 a
就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 . C( L. T/ v" K b% {0 l1 \/ [
件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可 \( B1 \" J5 \# N
能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然
* z0 b' D* u* x5 b6 j- k# a1 M是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 2 g! L8 Q( ~9 P& p
可能找到这十个最优解”的结论。 ) }1 z% U/ R0 B
时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决
7 E- z- H: f3 R的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才
. e- \0 S7 k% g可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就
W8 f% f$ D. j1 G+ _1 u: P找到这十个最优解，这都是可能的。
6 m5 N: w A) E0 w0 [+ S 科技的威力在解决此题与战胜SARS这件事上异曲同工。
4 J9 b; S3 R1 @/ y; M 擂台已经摆下：请给出这十个最优解。
/ x$ Q5 R2 k3 D$ H3 I x# Q补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问." t6 _. B4 C' h3 y$ h7 w5 d
# a* V- k6 d' o4 w/ c$ S# M
加一下难度给个第二问:
' Z( ]' S+ o7 r1 ?
, o" Y5 i2 D0 q! ?9 [% B0 r+ y6 g 证明:重排九宫最少步数为30步,并且只有十个最优解
作者: god 时间: 2005-3-30 23:40
765 765 765 7 5 75 475 475 475 475 4 5 45 145 145 145 145 1 5 15 153 153 153 3 @, l+ R' j9 G6 e* Y) F
432 43 4 3 463 463 63 163 163 1 3 173 173 73 073 073 0 3 043 043 04 042 042 ) B1 t: \" y- Y$ `
10 102 102 102 102 102 02 0 2 062 062 062 062 62 6 2 672 672 672 672 67 6 7
m* E/ q, x) i2 u$ f3 J- x" h6 N& E8 ^) o0 |
153 1 3 13 132 132 1 2 12 012 012 012 012
+ |# h6 _' [" ^4 @0 2 052 052 05 0 5 035 035 35 3 5 345 345 : l9 i! X. ]( b
647 647 647 647 647 647 647 647 647 6 7 67
# }2 g W1 W" {5 y9 _4 x2 m
! u8 I$ g8 E% d- H# B. _- V
" C3 G- k4 m1 I765 765 765 7 5 75 475 475 475 475 475 475 475 475 4 5 45 452 452 4 2 42 142 4 |+ E9 o' c5 X5 q% Z+ U
432 43 4 3 463 463 63 163 163 1 3 13 132 132 1 2 172 172 17 1 7 157 157 57
3 l. J2 a# y: [9 U( [: O% ^/ g10 102 102 102 102 102 02 0 2 062 062 06 0 6 036 036 036 036 036 036 036 036
0 _8 P( o: W9 b( f7 R: N
" o& A5 W7 y v1 e+ X% p142 142 142 142 142 1 2 12 012 012 012 012
' v* V0 @/ k3 j& l4 o. @3 X057 057 057 05 0 5 045 045 45 345 345 345
/ e2 M5 Q0 y r/ ?0 R 36 3 6 36 367 367 367 367 367 67 6 7 67
, n, U3 ?8 j, E; |, c0 P! I7 U* {) Z" B% N, R! ~8 n
+ A- y, o7 y8 J6 C- n' @% \* c/ j8 S
765 765 765 765 65 6 5 645 645 645 645 64 6 4 604 604 604 604 04 0 4 024 024 7 d$ [. b) k6 t, j' n% b, B8 v4 }: G
432 43 4 3 43 743 743 7 3 703 703 70 705 705 7 5 725 725 25 625 625 6 5 615
: k/ `- j% \! i$ b10 102 102 102 102 102 102 1 2 12 123 123 123 123 1 3 13 713 713 713 713 7 3
' G9 }9 a3 L" O& |0 q9 O: S% _9 z6 C" J2 N! c- {9 h" O: w
024 024 02 0 2 012 012 012 012 012 012 012 ! S9 G- }0 [ @) p0 I
615 61 614 614 6 4 634 634 34 3 4 34 345
7 A+ {& f1 `* S! ?; N73 735 735 735 735 7 5 75 675 675 675 67
/ U* h9 p& ^7 ~$ R9 G" x9 ]' }9 l* L- u: V+ r; `; {0 E, T2 ^2 o
( E( ~% F9 P2 ?! f( _8 D' \9 W( k$ d
765 765 765 765 765 765 765 7 5 75 753 753 753 753 7 3 73 173 173 173 173 1 3
, d' ]3 ^* L+ N- T/ s, I9 z; _432 43 4 3 43 143 143 1 3 163 163 16 162 162 1 2 152 152 52 052 052 0 2 072
' l1 B0 ?0 S+ ~: k1 W; p10 102 102 102 02 0 2 042 042 042 042 04 0 4 064 064 064 064 64 6 4 654 654 1 s/ O: Q8 E2 [. T
6 J* R+ i& g# u13 132 132 132 132 1 2 12 012 012 012 012 - V0 E; F6 U5 k, V( O z
072 07 074 074 0 4 034 034 34 3 4 34 345
& ~) E+ I3 Z$ M7 K* h" B8 }654 654 65 6 5 675 675 675 675 675 675 67 4 o6 I' d: A' L
1 r) C7 c ]3 {! `- q: A n' w
% I' N3 i# x/ M2 U6 \6 }- e& \765 765 765 765 765 765 765 765 765 765 765 7 5 75 175 175 175 175 1 5 15 152 2 _( K0 y; w$ I q
432 43 4 3 43 143 143 1 3 13 132 132 1 2 162 162 62 062 062 0 2 072 072 07 ( u2 x. X- @* @+ C1 t. T: E% z
10 102 102 102 02 0 2 042 042 04 0 4 034 034 034 034 34 3 4 364 364 364 364 0 M. B& g/ R* f7 e( }, s1 t8 e
* J3 J; I8 y& C; i; a5 c4 ]" A1 Z/ F
152 1 2 12 012 012 012 012 012 012 012 012
$ p* [8 `6 \* ^8 B6 c/ k! o0 7 057 057 57 357 357 357 35 3 5 345 345 : J. E- S8 X/ c5 O' S9 Q6 ~; N7 E
364 364 364 364 64 6 4 64 647 647 6 7 67
, v; ?* E, y* e! V' ~6 Z
. N, c% x" U8 O& R$ b5 n
% R! u( }( o+ @8 \. ^765 765 765 7 5 75 475 475 475 475 4 5 45 452 452 4 2 42 142 142 142 142 142 4 b, r$ p2 }% q% e! F/ u
432 432 4 2 462 462 62 162 162 1 2 172 172 17 1 7 157 157 57 357 357 357 35
5 x2 Z3 f7 Y4 ?% {. @* K$ w9 r! U# D10 1 0 130 130 130 130 30 3 0 360 360 360 360 360 360 360 360 60 6 0 60 607 " }, c1 ?5 b i
! x* Z5 ^0 q( @2 p0 W( `, y
142 142 142 142 142 1 2 12 012 012 012 012 ( m7 ~. _" W5 R" n9 t6 N
3 5 305 305 05 0 5 045 045 45 345 345 345 / x; z; H+ g$ a7 ]- d! X
607 6 7 67 367 367 367 367 367 67 6 7 67 3 U$ ~- h! n% I7 P1 M8 o( k* C
5 g. `5 C$ k; |- |- t
9 G1 f6 N5 y* w: A5 U/ E9 d' |) t765 765 765 765 65 6 5 645 645 64 6 4 624 624 624 624 62 6 2 632 632 632 632 ! q+ _9 |" O" w0 \" }, H$ R
432 432 4 2 42 742 742 7 2 72 725 725 7 5 735 735 73 734 734 7 4 704 704 04
9 o3 ?; y: G5 Y) E10 1 0 130 130 130 130 130 130 130 130 130 1 0 10 105 105 105 105 1 5 15 715 & P( p' f8 x% m E
' B# s9 ^1 j& ]# M
32 3 2 302 302 302 302 02 0 2 012 012 012
: [5 G- r: [5 a) w0 M0 f604 604 6 4 614 614 14 314 314 3 4 34 345 & ^+ `0 t. ]0 n/ @9 ~( L- x8 b! J
715 715 715 7 5 75 675 675 675 675 675 67
( X& u/ _) n8 o2 X) |5 ^9 b% Q: O# N" ^6 ?, T8 M
2 s& t6 `8 T+ n9 u& J: |# r2 X
765 765 765 765 765 765 765 765 65 6 5 625 625 62 6 2 602 602 602 602 02 0 2
' T. E& N( z5 o0 b5 ~; `432 432 4 2 42 420 420 420 20 720 720 7 0 70 705 705 7 5 715 715 15 615 615
1 g; n8 W. }7 w* \" ?10 1 0 130 130 13 1 3 13 413 413 413 413 413 413 413 413 4 3 43 743 743 743
) n: d, ?1 Y& c! l/ n
- ^; F7 l6 i% C3 T012 012 012 012 012 012 012 012 012 012 012
/ z0 v7 y( [ l* ]6 5 645 645 64 6 4 634 634 34 3 4 34 345 6 {: [& y* E' _+ ]# ~4 h
743 7 3 73 735 735 7 5 75 675 675 675 67
! x! J; x6 B& l! a/ S# ^! c4 s* n. P6 l6 b; I9 @
/ C a3 n( l( P; ~( f
765 765 765 765 65 6 5 635 635 635 635 635 635 635 635 635 635 35 3 5 325 325 % X; E; O2 z4 Y" D* w* W, |
432 432 432 32 732 732 7 2 72 472 472 4 2 42 420 420 420 20 620 620 6 0 60 ; c/ P5 O7 G$ e7 c
10 1 0 10 410 410 410 410 410 10 1 0 170 170 17 1 7 17 417 417 417 417 417
7 n6 d& D$ J. S* P: ]. [2 J# I8 W! y( s
32 3 2 302 302 302 302 02 0 2 012 012 012 3 b! U! O( G3 K' u
605 605 6 5 615 615 15 315 315 3 5 345 345 9 E; a- X" }2 C2 h
417 417 417 4 7 47 647 647 647 647 6 7 67
5 I! T! G. N/ p- S5 M/ T! w$ [6 f" I3 c5 q2 _
, Y- v$ y& u" Q8 V5 d
765 765 765 765 65 6 5 635 635 635 635 635 635 35 3 5 325 325 32 3 2 302 302 8 @6 ^" I! d/ e; T% |& p/ {
432 432 432 32 732 732 7 2 72 720 720 720 20 620 620 6 0 60 605 605 6 5 645
& n% E7 s7 r- d4 c10 1 0 10 410 410 410 410 410 41 4 1 41 741 741 741 741 741 741 741 741 7 1 ( H" S6 O3 I# E( f4 j
6 j' h+ s/ c% X" O302 302 302 302 302 302 02 0 2 012 012 012 9 l. y' M$ h. T# r- A: N' b
645 64 6 4 614 614 14 314 314 3 4 34 345 7 d4 g0 h& s. `( h3 u; R" h% c, Z
71 715 715 7 5 75 675 675 675 675 675 67
作者: fly_eager 时间: 2005-4-27 16:10
很有兴趣！
作者: 罗炳 时间: 2005-5-2 14:44
请教
后面的数字是什么意思啊
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |