数学建模社区-数学中国
标题: [灌水]喜欢迎接挑战的请进来！ [打印本页]
作者: god 时间: 2005-3-30 23:40
标题: [灌水]喜欢迎接挑战的请进来！
喜欢迎接挑战的请进来！ & Z" D0 X2 J( i! M- |& _. P
《小擂台》 f+ L, S4 e* T- A; B
这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所
9 m( C/ J" `9 D( _3 S3 |( {% T0 d! b以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于 5 w) V# F. v' r' B. r( H
我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 I F8 Z8 w$ [5 M
余生活，何况这个题目在今天研究，已经具有双重的考验作用了。 # z, w7 |' F- m- G+ Q% [/ O
不要去找现成的答案。也不是那么好找。 0 j' A, S: O" g" M6 X
一是完全用我们的大脑来解决问题，这个难度是有相当档次的。
; ~" m1 X+ O+ \* V 二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出 8 R4 z4 _, E0 b: k: d9 r) |2 z6 Y+ X
一个解决问题的搜索程序，解决这个问题。
0 S1 L3 M0 A" z
9 h3 q$ n: o2 x' Q6 Z 1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重 . z) G( m) E: ~4 I% @' {# p' e7 C
排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下：
2 _5 Z0 Q7 h& b3 b2 q在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格
, {! ?* r" `7 t( Y/ ^2 G! v开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空
: [1 M c2 I* Z8 P! o格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任 + D6 c% v$ B! m' k2 C
意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、
2 E- ]$ K4 I* |$ w7 q0 b) C6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 1 A9 b- e9 T6 T8 N
为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步 + `8 Q# [ l& \) j4 R
以内完成就是智商很高的体现了。 : V7 t e! g6 O' {0 G; L
2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 8 h4 I6 C# p5 I
但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 # s% K5 j l# m$ l0 _* P
事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段 ( Q' H- |. ]8 i) x2 c d* |/ n; k
——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小 8 B" w9 g/ A A* x* m. T
时的计算机运算时间，才找到了全部的最优解。 # J* }/ L, N' \- ^+ k; \
他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能 ( v l) ~3 U1 w2 {" Y
完成的。 + S3 P. A8 @5 [) t& m
事实上，在20多年前当这个题目在国内公布之后，在短短的半年内， 1 Z F: }2 j4 ~! t: m6 v" T
就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事
( ]! O8 }; N: _! d0 c5 [6 |件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可 * ?* O7 W& m- J0 o: J
能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然
- l. t; H k4 E. U* M- x是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 - |7 @" @, W; [4 B, F& m
可能找到这十个最优解”的结论。
0 Y4 d/ l# O8 O/ j 时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决 ( l. M) e) t7 }: F9 O6 s( J1 @
的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 3 Q2 y- g' g$ I8 A5 b3 J8 _
可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就 % X, U8 Q- V2 \, A" {$ ?
找到这十个最优解，这都是可能的。
; s v7 [1 U7 C# g1 ^$ R4 d$ B$ w7 m 科技的威力在解决此题与战胜SARS这件事上异曲同工。
& R x) M* d- x+ c: F* z; n% V' m 擂台已经摆下：请给出这十个最优解。 , ~0 ^5 j- c, x" u3 R4 _, e
补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问. e9 f- R+ ]# w
+ t) N& S5 j) X+ ]* [ 加一下难度给个第二问:* |5 t f- R- L' l% l7 L U
0 ^# U% E% R: P2 E* X
证明:重排九宫最少步数为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
2 o+ m( @" e: m1 q432 43 4 3 463 463 63 163 163 1 3 173 173 73 073 073 0 3 043 043 04 042 042 - D% Z; \, A1 W+ y8 w0 z7 Q
10 102 102 102 102 102 02 0 2 062 062 062 062 62 6 2 672 672 672 672 67 6 7 8 O8 C+ v6 D4 l% o. E: |# J
1 |1 y+ j. F3 Y% q- |, g2 T: ?153 1 3 13 132 132 1 2 12 012 012 012 012
P* |- W2 r$ N$ [. Z0 2 052 052 05 0 5 035 035 35 3 5 345 345 4 L' n& K1 S+ M: Q. j) P5 E
647 647 647 647 647 647 647 647 647 6 7 67
7 e& A* `, o& y8 M) V2 N+ \, H* ~ q8 ~3 b
, n7 Z; }3 C& T5 x5 [$ \! s* |: v
765 765 765 7 5 75 475 475 475 475 475 475 475 475 4 5 45 452 452 4 2 42 142
4 v( v) `: i @. F4 _432 43 4 3 463 463 63 163 163 1 3 13 132 132 1 2 172 172 17 1 7 157 157 57
& B. ~# P- L: _+ V8 U$ t- [" N2 B10 102 102 102 102 102 02 0 2 062 062 06 0 6 036 036 036 036 036 036 036 036
5 B# t$ T+ [! h6 ~) n$ n" c' z o( T: G7 |) K" P
142 142 142 142 142 1 2 12 012 012 012 012
& S E) P6 @* \& o057 057 057 05 0 5 045 045 45 345 345 345 m2 \) s8 E! i2 I1 l- j% n
36 3 6 36 367 367 367 367 367 67 6 7 67
9 o4 [" \8 x4 C# ^) J J9 N4 k8 k9 l" M6 N# D4 g, f' w0 ?- a
+ ]9 _* y& l8 R& k: J
765 765 765 765 65 6 5 645 645 645 645 64 6 4 604 604 604 604 04 0 4 024 024 H# F' M( I8 B# @# u/ l
432 43 4 3 43 743 743 7 3 703 703 70 705 705 7 5 725 725 25 625 625 6 5 615 " y) K# w6 f; i& a, K3 q
10 102 102 102 102 102 102 1 2 12 123 123 123 123 1 3 13 713 713 713 713 7 3
/ G6 p; s. ~( B1 {9 U9 K* w/ T3 s
W1 ]* K! Q1 M- [* f024 024 02 0 2 012 012 012 012 012 012 012 & I& F8 i' u! f$ \/ B4 n
615 61 614 614 6 4 634 634 34 3 4 34 345
% P5 V" g* b: B% U+ D$ l. z73 735 735 735 735 7 5 75 675 675 675 67 " n9 P# c) e4 \/ P. O$ n' I
) A) @) y. W" W L9 U4 a# a$ d; }, E0 ^2 T( B+ h1 a1 @7 B; s
765 765 765 765 765 765 765 7 5 75 753 753 753 753 7 3 73 173 173 173 173 1 3
; z& a( `# _7 t0 f/ k# J5 ]4 ~432 43 4 3 43 143 143 1 3 163 163 16 162 162 1 2 152 152 52 052 052 0 2 072
+ k! _8 ^. x8 f10 102 102 102 02 0 2 042 042 042 042 04 0 4 064 064 064 064 64 6 4 654 654
+ M/ e$ J( Q! D# t3 d3 z6 _0 O. |, _
13 132 132 132 132 1 2 12 012 012 012 012 ' M0 U' v! m: ]$ ~5 V
072 07 074 074 0 4 034 034 34 3 4 34 345 5 m7 F) U% C" w' ^) R( ]% _6 ?9 M
654 654 65 6 5 675 675 675 675 675 675 67
! {$ P+ y& X0 H! E
6 A3 o8 W% l% `8 @5 s6 X; N) P
) j3 n# D8 X* z7 {* a/ O3 Z y7 X765 765 765 765 765 765 765 765 765 765 765 7 5 75 175 175 175 175 1 5 15 152 $ m4 \0 S' Y% b' {- g+ E. O% h
432 43 4 3 43 143 143 1 3 13 132 132 1 2 162 162 62 062 062 0 2 072 072 07
2 f b$ M8 C; d: u6 l10 102 102 102 02 0 2 042 042 04 0 4 034 034 034 034 34 3 4 364 364 364 364
7 I% ? @8 F* L& W, q- l: o# U" N: c- M: F6 H
152 1 2 12 012 012 012 012 012 012 012 012 ) J$ H! t3 G; [3 K' {# }% [. g
0 7 057 057 57 357 357 357 35 3 5 345 345 : ?5 M9 o6 n" k; z: }3 O4 L
364 364 364 364 64 6 4 64 647 647 6 7 67 3 e& N8 `; I( p8 T* j/ y) d
, v: U" L" e9 @" i' z
. _- K0 N# S6 A
765 765 765 7 5 75 475 475 475 475 4 5 45 452 452 4 2 42 142 142 142 142 142
5 u+ o9 t* r6 Y4 f432 432 4 2 462 462 62 162 162 1 2 172 172 17 1 7 157 157 57 357 357 357 35
+ c/ w, q& e$ Q/ E: \10 1 0 130 130 130 130 30 3 0 360 360 360 360 360 360 360 360 60 6 0 60 607
3 H1 F( ~+ \: V( N$ ]: ^, }, ?
( @& ~" h/ c* X" Y; z142 142 142 142 142 1 2 12 012 012 012 012
1 e. _7 @( _* {; r3 5 305 305 05 0 5 045 045 45 345 345 345 / @( S6 ]5 z5 ]9 U6 c: W( ?
607 6 7 67 367 367 367 367 367 67 6 7 67
7 k4 k0 f. W0 S6 C- J& F; u5 F: [1 Z2 S6 B* m
4 l1 D& J U3 r( ~) z
765 765 765 765 65 6 5 645 645 64 6 4 624 624 624 624 62 6 2 632 632 632 632 , V6 P- H8 I* L( M" D3 b9 |
432 432 4 2 42 742 742 7 2 72 725 725 7 5 735 735 73 734 734 7 4 704 704 04 & h+ o9 U$ D) [0 |' R
10 1 0 130 130 130 130 130 130 130 130 130 1 0 10 105 105 105 105 1 5 15 715
' h, J( ~+ L6 r6 I
* R! ^) D% a9 f 32 3 2 302 302 302 302 02 0 2 012 012 012 9 \/ s% K; U9 e) M8 S( J) _
604 604 6 4 614 614 14 314 314 3 4 34 345
4 D o$ Z5 v7 g715 715 715 7 5 75 675 675 675 675 675 67 3 c$ y" Q: W* z6 _% \
+ q4 Z2 j+ W' z7 H; d) G& u# Z. q
( v5 w0 M+ f; R1 }3 N b765 765 765 765 765 765 765 765 65 6 5 625 625 62 6 2 602 602 602 602 02 0 2
' R/ J+ ]6 y8 x' _! f432 432 4 2 42 420 420 420 20 720 720 7 0 70 705 705 7 5 715 715 15 615 615 , f$ U) R* c5 |# I
10 1 0 130 130 13 1 3 13 413 413 413 413 413 413 413 413 4 3 43 743 743 743 : Z6 w; x7 K: Z u. `8 y" @
r0 R) g! I$ I) b1 e7 q012 012 012 012 012 012 012 012 012 012 012 , G9 g5 ]5 G- t/ m, R0 V
6 5 645 645 64 6 4 634 634 34 3 4 34 345
7 P3 s a! E |743 7 3 73 735 735 7 5 75 675 675 675 67 / }: D- @# T F! n+ d
) e& n: j: h8 K7 o8 W
K( a6 V8 W/ J# C4 j5 |765 765 765 765 65 6 5 635 635 635 635 635 635 635 635 635 635 35 3 5 325 325
% O, ~0 A# f- I4 M' T6 W1 o432 432 432 32 732 732 7 2 72 472 472 4 2 42 420 420 420 20 620 620 6 0 60 / u' T. [: }6 d% P/ y5 J
10 1 0 10 410 410 410 410 410 10 1 0 170 170 17 1 7 17 417 417 417 417 417 , e4 S5 m0 E) A
7 K8 z9 Z% J2 e6 T1 R6 g( Z- u1 A' k
32 3 2 302 302 302 302 02 0 2 012 012 012 2 L+ s# B$ B/ C' Y
605 605 6 5 615 615 15 315 315 3 5 345 345
; ^& H0 H+ Q- ^& I9 Y; ?417 417 417 4 7 47 647 647 647 647 6 7 67
$ W! ^1 l" I0 O" ?: k* o O& J3 H$ v9 i4 ~8 u, t
) R+ ^7 t& M0 n4 b* G1 J
765 765 765 765 65 6 5 635 635 635 635 635 635 35 3 5 325 325 32 3 2 302 302
/ `2 ~8 F2 U n0 C, N" q5 Z432 432 432 32 732 732 7 2 72 720 720 720 20 620 620 6 0 60 605 605 6 5 645 9 }$ g" k0 ]5 s" {: f! R3 I
10 1 0 10 410 410 410 410 410 41 4 1 41 741 741 741 741 741 741 741 741 7 1 - m& c. A0 K! k* q
- J$ V& x( F2 W2 s i w e
302 302 302 302 302 302 02 0 2 012 012 012
: {: n7 N- x7 r0 {# V2 A645 64 6 4 614 614 14 314 314 3 4 34 345 % ]# V( G4 i3 N: M' f4 M2 B
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 |