数学建模社区-数学中国
标题: [灌水]喜欢迎接挑战的请进来！ [打印本页]
作者: god 时间: 2005-3-30 23:40
标题: [灌水]喜欢迎接挑战的请进来！
喜欢迎接挑战的请进来！
0 A* E8 x7 y. A4 q, Z《小擂台》 7 v' H8 ? Z% n+ s- L
这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所
4 g3 O1 x. j* `) |. ~0 D% i以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于 ! v- Z- D$ k4 _) g: E
我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 : I8 q3 N8 I' j* A6 }+ i
余生活，何况这个题目在今天研究，已经具有双重的考验作用了。
" H8 }. [, P( V6 ?9 ^+ M* m 不要去找现成的答案。也不是那么好找。 & o% o; ~' D" [" ]( \+ h6 d
一是完全用我们的大脑来解决问题，这个难度是有相当档次的。 # L( \. w2 ]1 ~8 C
二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出
6 r$ ]; ^- K9 B7 R0 c; z V一个解决问题的搜索程序，解决这个问题。
9 Z5 T8 P+ w/ G5 d
* @/ o& I" n `/ }" c; p. W 1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重
! t7 z4 e" M0 \8 s3 X+ v排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下：
! L. B5 D# D8 t$ N3 U# e在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格
; R! U! ~/ P5 B% r% y开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空
w$ e1 q! H; _/ k* b) i6 y格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任
+ y: _+ o0 R# Q+ r' e意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、
$ [, J6 N) [2 U+ |6 Q4 M" u: u! u- N6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 ' f2 O% Z/ l' K$ H$ |
为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步
( \" p+ {7 T9 g4 {/ M7 O以内完成就是智商很高的体现了。 7 W' }& j* g+ |4 {1 w
2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。
2 V7 w" X, e D. z: B7 T 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 ' t* L% G7 S3 Z6 r4 K B
事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段 & |* @9 l+ |, Z4 x
——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小 ( f* c8 H) {/ v O7 b, f( a' {
时的计算机运算时间，才找到了全部的最优解。 2 n8 M e/ |7 J! K/ o# o
他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能
5 y' H- n; I' k2 v, O s2 z. E完成的。 * Y+ K- i/ @6 R! D
事实上，在20多年前当这个题目在国内公布之后，在短短的半年内，
8 _* E2 _8 x9 t6 Q W3 X. J就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 9 M8 P' A- s2 [7 B
件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可
; f1 z( u/ C$ z7 P, s& L( n能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然
: O' W4 q' J3 x. G: w$ M: o O9 w {是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不
$ G& A3 ~" S8 O) L% S可能找到这十个最优解”的结论。 ! ^" M% V7 y$ o! G) G
时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决 6 s+ `. `) f8 m: m8 I3 d
的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 ' U, l' z9 n$ [- x2 l' C
可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就
5 v4 I. C1 n7 D0 [6 i找到这十个最优解，这都是可能的。 8 f; I- C6 r" D' h/ Q2 ?' w
科技的威力在解决此题与战胜SARS这件事上异曲同工。
, X1 ]. J7 a6 m4 |' o4 z" U 擂台已经摆下：请给出这十个最优解。
* h* j+ m7 `9 d; D$ [) c1 U补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问.. t5 }3 r0 t* w w: i6 D1 t
5 _% I' |8 H6 Z: s# r" ^
加一下难度给个第二问:
7 f8 G7 c( j: ?7 V6 y9 L, D: ?! v+ t5 D2 e7 M7 a
证明:重排九宫最少步数为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 9 ], V% X+ _$ ]- F- {' `" {; h# {
432 43 4 3 463 463 63 163 163 1 3 173 173 73 073 073 0 3 043 043 04 042 042 " B9 m8 w" [: }2 t% o
10 102 102 102 102 102 02 0 2 062 062 062 062 62 6 2 672 672 672 672 67 6 7 & p5 A0 m! Q! }) x( ]7 R
1 h# z, i& ?- o2 l. g# O+ c153 1 3 13 132 132 1 2 12 012 012 012 012 % C8 [( I0 `% C! b2 w5 C9 P! s: o
0 2 052 052 05 0 5 035 035 35 3 5 345 345 : }; R6 \/ W n) Q. J
647 647 647 647 647 647 647 647 647 6 7 67 W- e# m8 a8 c+ @% c
5 A) X' K' S. @# o8 x# }& u
( K$ B. ]5 o& s) q, k8 }$ T, n8 P
765 765 765 7 5 75 475 475 475 475 475 475 475 475 4 5 45 452 452 4 2 42 142
- z! T! L! P A/ [/ t432 43 4 3 463 463 63 163 163 1 3 13 132 132 1 2 172 172 17 1 7 157 157 57 - g& ?$ b0 K5 S' T/ R1 c
10 102 102 102 102 102 02 0 2 062 062 06 0 6 036 036 036 036 036 036 036 036 6 \2 U5 ~8 f$ K- M5 [
% d; k9 {8 l. d, g, h142 142 142 142 142 1 2 12 012 012 012 012
! m( I3 U; }. p- t1 Z3 k+ W057 057 057 05 0 5 045 045 45 345 345 345 8 H0 P9 L1 I+ ]$ v/ P Y! V
36 3 6 36 367 367 367 367 367 67 6 7 67
/ b4 v; p4 n( Y' u" P& @: |, W/ \& S0 ^7 m7 n8 ^! ]) U- T
) d# x1 ^& L' N765 765 765 765 65 6 5 645 645 645 645 64 6 4 604 604 604 604 04 0 4 024 024
0 U( _0 ~+ Y3 F432 43 4 3 43 743 743 7 3 703 703 70 705 705 7 5 725 725 25 625 625 6 5 615
' l) I. C% x8 X% s- y- h: h10 102 102 102 102 102 102 1 2 12 123 123 123 123 1 3 13 713 713 713 713 7 3
, q: Z$ K4 ?, Q' D5 k6 n, h# T
" O$ L+ @ t1 e# }024 024 02 0 2 012 012 012 012 012 012 012 # U* |+ i/ k* }) @. l
615 61 614 614 6 4 634 634 34 3 4 34 345 3 _7 d; E" |, V3 }+ X
73 735 735 735 735 7 5 75 675 675 675 67
$ b/ o( I% i) F3 ]; ~
' d1 A4 y( X; f/ f4 ^+ Q! z2 q
$ o( t' ~. d+ B765 765 765 765 765 765 765 7 5 75 753 753 753 753 7 3 73 173 173 173 173 1 3 + R- q5 p$ o) I
432 43 4 3 43 143 143 1 3 163 163 16 162 162 1 2 152 152 52 052 052 0 2 072
3 D5 H0 N7 r7 L0 \10 102 102 102 02 0 2 042 042 042 042 04 0 4 064 064 064 064 64 6 4 654 654 % ]# `; k/ g7 I3 I% r' h
: Z4 [1 L, ]+ T13 132 132 132 132 1 2 12 012 012 012 012 . Z' t2 K# \4 m" ~& I* N
072 07 074 074 0 4 034 034 34 3 4 34 345
6 Q, r+ H( K( `/ e5 V0 C, Q$ x654 654 65 6 5 675 675 675 675 675 675 67 0 g- f! P" `" Y' _, k! w: |
; |; p2 S+ M" C; g
, Q' z3 |, [9 `5 w5 ]5 E$ Q765 765 765 765 765 765 765 765 765 765 765 7 5 75 175 175 175 175 1 5 15 152
4 h# D( B# Y) B$ Y6 ^/ U432 43 4 3 43 143 143 1 3 13 132 132 1 2 162 162 62 062 062 0 2 072 072 07
9 ~- j) ^, \ C10 102 102 102 02 0 2 042 042 04 0 4 034 034 034 034 34 3 4 364 364 364 364 ! Y& i; n. n+ x2 j0 J; @! f9 P
; Y! c5 ^ p' O" h9 O
152 1 2 12 012 012 012 012 012 012 012 012
' d5 @' g0 \. r; D/ N+ o9 P0 7 057 057 57 357 357 357 35 3 5 345 345 2 n# ^( Y% J/ ]5 z3 k0 m8 Z; y
364 364 364 364 64 6 4 64 647 647 6 7 67 , q/ E8 A/ l2 p
% K, B1 D, S5 ^- `+ U* |8 |* t
# ` D( C' I' `' Y3 J' _765 765 765 7 5 75 475 475 475 475 4 5 45 452 452 4 2 42 142 142 142 142 142 - d4 L \9 R% ~( B2 q
432 432 4 2 462 462 62 162 162 1 2 172 172 17 1 7 157 157 57 357 357 357 35
$ q% ]1 E2 o$ Y- T: P! ^10 1 0 130 130 130 130 30 3 0 360 360 360 360 360 360 360 360 60 6 0 60 607
; d! T/ Q0 D4 i; p7 }% ?, n7 |; d
9 s0 w- ?+ _0 d9 Y- r4 m142 142 142 142 142 1 2 12 012 012 012 012
" l& ^' o+ e3 r! _" S3 5 305 305 05 0 5 045 045 45 345 345 345 5 H$ R, l% R, m3 \& L0 F; k
607 6 7 67 367 367 367 367 367 67 6 7 67
9 R1 ~5 r2 U: `( B* _% z) h% x2 r9 o- y" y
5 n3 I# J) M4 u O/ G! `
765 765 765 765 65 6 5 645 645 64 6 4 624 624 624 624 62 6 2 632 632 632 632 ( u! j/ h i- R6 o0 l h
432 432 4 2 42 742 742 7 2 72 725 725 7 5 735 735 73 734 734 7 4 704 704 04 ! m4 s- p1 F4 K
10 1 0 130 130 130 130 130 130 130 130 130 1 0 10 105 105 105 105 1 5 15 715 0 i5 Q: I4 u( M
7 Y! ~& n: j# e( f# A' X$ H8 m
32 3 2 302 302 302 302 02 0 2 012 012 012 9 |( u! _% x. N) d* x. X# o8 o7 Q
604 604 6 4 614 614 14 314 314 3 4 34 345 , v' y# Z* t5 |" V" [
715 715 715 7 5 75 675 675 675 675 675 67
5 U7 \ }( _, S; l
[3 l5 f; |3 ?2 t) M- F# y6 ~0 ]
# r4 t o1 u5 ]. s- `765 765 765 765 765 765 765 765 65 6 5 625 625 62 6 2 602 602 602 602 02 0 2 : m% o, Z. J$ j: v2 r( y6 c+ ]
432 432 4 2 42 420 420 420 20 720 720 7 0 70 705 705 7 5 715 715 15 615 615
. B/ h, v, G+ F8 _- \3 r# w' @7 B10 1 0 130 130 13 1 3 13 413 413 413 413 413 413 413 413 4 3 43 743 743 743
$ V+ y% W8 N! o( V7 j9 s6 Q: }+ ]+ ?' i, g8 X* Z: ?/ L2 b
012 012 012 012 012 012 012 012 012 012 012
; L) r5 `$ |2 w' p( l, i$ f0 N6 5 645 645 64 6 4 634 634 34 3 4 34 345 & H2 ]; ?5 v% }& H* h8 U
743 7 3 73 735 735 7 5 75 675 675 675 67 * X: b6 W4 P( U& v7 m: [7 @9 d8 O
9 \5 ]" ~ ]4 Q: R2 u7 T$ h8 A2 T+ s: ^" ?- \9 l" Q
765 765 765 765 65 6 5 635 635 635 635 635 635 635 635 635 635 35 3 5 325 325
J. q+ m1 _' |5 z' C; ^( }( i432 432 432 32 732 732 7 2 72 472 472 4 2 42 420 420 420 20 620 620 6 0 60
( R0 z: x' x3 ]5 w1 O1 n, Q+ V10 1 0 10 410 410 410 410 410 10 1 0 170 170 17 1 7 17 417 417 417 417 417 # L) R) U; g n4 m
+ J6 U% p9 H1 r1 L0 K$ X32 3 2 302 302 302 302 02 0 2 012 012 012 . |4 x- z% @: |1 t' n2 F0 l/ |
605 605 6 5 615 615 15 315 315 3 5 345 345
% J/ d, V$ K g0 V8 s$ r' }417 417 417 4 7 47 647 647 647 647 6 7 67
* x ~1 z8 F2 w7 U
; I& V0 W. N5 j4 p' u% F: } Y, M8 M z# j9 Y" P
765 765 765 765 65 6 5 635 635 635 635 635 635 35 3 5 325 325 32 3 2 302 302
- Y o8 e, u2 Z432 432 432 32 732 732 7 2 72 720 720 720 20 620 620 6 0 60 605 605 6 5 645 1 O0 c5 h+ [3 K' f: P* `- T) K! I
10 1 0 10 410 410 410 410 410 41 4 1 41 741 741 741 741 741 741 741 741 7 1 ! X% r( j" e2 W) e6 c2 f
, d( V$ }! G; n0 j/ y302 302 302 302 302 302 02 0 2 012 012 012
+ k E, [" E) |" g645 64 6 4 614 614 14 314 314 3 4 34 345
' L2 v; u! q/ n: X( F7 e71 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 |