数学建模社区-数学中国

标题: [灌水]喜欢迎接挑战的请进来！ [打印本页]

---

作者: god    时间: 2005-3-30 23:40
标题: [灌水]喜欢迎接挑战的请进来！

喜欢迎接挑战的请进来！ 7 ]4 i f0 L6 y2 U2 x9 Z2 q《小擂台》 " B& x( E, ^) v$ h# k3 ^ 这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所 ' @ ]6 }: T$ {以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于 我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 余生活，何况这个题目在今天研究，已经具有双重的考验作用了。 不要去找现成的答案。也不是那么好找。 一是完全用我们的大脑来解决问题，这个难度是有相当档次的。 二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出 / T6 d8 T2 [' u3 z4 q一个解决问题的搜索程序，解决这个问题。 1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重 # p" \ B. n+ k0 D* |排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下： 在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格 # l# b* R/ e( H9 J4 Q, |开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空 格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任 ( @# F8 g0 h7 L% \/ t) F5 ^% K意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 3 Q2 `! V/ S4 ~6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步 ! g$ O2 L2 h% \以内完成就是智商很高的体现了。 - n6 T- ^9 |9 L 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 + ~. g; [, ]& l8 e9 B2 d 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 ; S- Z2 q# d. a& \$ @ 事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段 6 v3 b7 n- j; S: c! Q2 p——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小 时的计算机运算时间，才找到了全部的最优解。 ) ~* R8 ?* u, s/ q B 他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能 + P, j* k6 H# z, G8 Y0 B完成的。 事实上，在20多年前当这个题目在国内公布之后，在短短的半年内， 就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 ; e" y( l( T5 S( T. B件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可 能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然 是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 # y5 i0 C7 G7 c" [/ Q2 N4 u3 P可能找到这十个最优解”的结论。 时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决 4 J5 e- {8 m% |& X0 C的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就 找到这十个最优解，这都是可能的。 科技的威力在解决此题与战胜SARS这件事上异曲同工。 " d$ G* M3 `8 B+ Y1 ?9 F3 f$ z 擂台已经摆下：请给出这十个最优解。 ) N; ], `& T& E( c) S/ E, G% l3 H1 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
5 m7 P! R: z' _- F( `432 43  4 3 463 463  63 163 163 1 3 173 173  73 073 073 0 3 043 043 04  042 042
- `: O% f1 S9 \* A) _9 x10  102 102 102 102 102  02 0 2 062 062 062 062  62 6 2 672 672 672 672 67  6 7

153 1 3 13  132 132 1 2  12 012 012 012 012
, ]- S) D0 i" Y% _- j0 2 052 052 05  0 5 035 035  35 3 5 345 345
" d7 ~$ q! X, O$ g/ z% s8 Y647 647 647 647 647 647 647 647 647 6 7 67  


# e0 g1 G3 [7 I8 S  Q765 765 765 7 5  75 475 475 475 475 475 475 475 475 4 5 45  452 452 4 2  42 142
432 43  4 3 463 463  63 163 163 1 3 13  132 132 1 2 172 172 17  1 7 157 157  57
10  102 102 102 102 102  02 0 2 062 062 06  0 6 036 036 036 036 036 036 036 036
9 G3 y  q  R7 M' b8 S, D5 n/ a
0 d5 W' Y, B9 j3 j142 142 142 142 142 1 2  12 012 012 012 012
057 057 057 05  0 5 045 045  45 345 345 345
36 3 6 36  367 367 367 367 367  67 6 7 67  


765 765 765 765  65 6 5 645 645 645 645 64  6 4 604 604 604 604  04 0 4 024 024
# N. g, k* E) R2 f9 c. y0 {432 43  4 3  43 743 743 7 3 703 703 70  705 705 7 5 725 725  25 625 625 6 5 615
10  102 102 102 102 102 102 1 2 12  123 123 123 123 1 3  13 713 713 713 713 7 3
* }# K; \7 L) K7 q/ s- V4 Q# r/ U
024 024 02  0 2 012 012 012 012 012 012 012
' U7 F9 P2 W6 t: n  u615 61  614 614 6 4 634 634  34 3 4 34  345
! ?4 F2 D* O* c5 I73  735 735 735 735 7 5  75 675 675 675 67  
9 P9 Y% g2 v/ A
8 h6 `3 W6 u3 g2 _8 v& L) k8 b" h4 N# t
7 a/ C' B$ ]% z4 P765 765 765 765 765 765 765 7 5 75  753 753 753 753 7 3  73 173 173 173 173 1 3
) q0 f7 ~9 l9 u/ f! k432 43  4 3  43 143 143 1 3 163 163 16  162 162 1 2 152 152  52 052 052 0 2 072
- m5 c- ^# U% n- d  s. q6 p10  102 102 102  02 0 2 042 042 042 042 04  0 4 064 064 064 064  64 6 4 654 654
' ], ^; r* n& @# g- u4 G( n8 M2 P! _, L
13  132 132 132 132 1 2  12 012 012 012 012
1 f! F. ]5 X6 H* V* h072 07  074 074 0 4 034 034  34 3 4 34  345
$ k8 z! }* \6 g' Q! a2 l654 654 65  6 5 675 675 675 675 675 675 67  

: i2 o. x# h( m3 b- S9 D& M% [: x2 x, e
765 765 765 765 765 765 765 765 765 765 765 7 5  75 175 175 175 175 1 5 15  152
432 43  4 3  43 143 143 1 3 13  132 132 1 2 162 162  62 062 062 0 2 072 072 07  
9 u4 h2 }8 n0 ~9 i9 V, h10  102 102 102  02 0 2 042 042 04  0 4 034 034 034 034  34 3 4 364 364 364 364
7 S# ]6 z" e0 f2 o
, |* p3 \0 [. c152 1 2  12 012 012 012 012 012 012 012 012
0 7 057 057  57 357 357 357 35  3 5 345 345
364 364 364 364  64 6 4 64  647 647 6 7 67  

! e" N. E, f* m' T+ m4 o' f9 t" h
765 765 765 7 5  75 475 475 475 475 4 5 45  452 452 4 2  42 142 142 142 142 142
432 432 4 2 462 462  62 162 162 1 2 172 172 17  1 7 157 157  57 357 357 357 35  
1 C/ K. B, u4 j4 l+ U' l& U10  1 0 130 130 130 130  30 3 0 360 360 360 360 360 360 360 360  60 6 0 60  607
( ]8 _+ \. p( {( K
. W- O. r# o9 S" B% y142 142 142 142 142 1 2  12 012 012 012 012
3 5 305 305  05 0 5 045 045  45 345 345 345
607 6 7  67 367 367 367 367 367  67 6 7 67  


765 765 765 765  65 6 5 645 645 64  6 4 624 624 624 624 62  6 2 632 632 632 632
432 432 4 2  42 742 742 7 2 72  725 725 7 5 735 735 73  734 734 7 4 704 704  04
+ A- n: i- H# [9 |6 [6 j9 a10  1 0 130 130 130 130 130 130 130 130 130 1 0 10  105 105 105 105 1 5  15 715
. y9 B  p9 H5 j2 `! ]
32 3 2 302 302 302 302  02 0 2 012 012 012
604 604 6 4 614 614  14 314 314 3 4 34  345
) G4 D9 ~0 Y1 q7 r4 v! e" J715 715 715 7 5  75 675 675 675 675 675 67  


765 765 765 765 765 765 765 765  65 6 5 625 625 62  6 2 602 602 602 602  02 0 2
432 432 4 2 42  420 420 420  20 720 720 7 0 70  705 705 7 5 715 715  15 615 615
10  1 0 130 130 13  1 3  13 413 413 413 413 413 413 413 413 4 3  43 743 743 743
% J: U& @5 I6 Q, w$ z6 n
! V3 @% X! j. O: T012 012 012 012 012 012 012 012 012 012 012
* v1 \' a, h) ^6 5 645 645 64  6 4 634 634  34 3 4 34  345
743 7 3 73  735 735 7 5  75 675 675 675 67  

- f* W9 C' Q; a% N9 a
" i% C; y: [. o+ ^2 z+ U. p8 x, I765 765 765 765  65 6 5 635 635 635 635 635 635 635 635 635 635  35 3 5 325 325
432 432 432  32 732 732 7 2  72 472 472 4 2 42  420 420 420  20 620 620 6 0 60  
10  1 0  10 410 410 410 410 410  10 1 0 170 170 17  1 7  17 417 417 417 417 417
7 Q" y& f6 I2 @
/ W0 @; ]0 L! ^% V' N, A" P- N/ ]8 z32  3 2 302 302 302 302  02 0 2 012 012 012
605 605 6 5 615 615  15 315 315 3 5 345 345
417 417 417 4 7  47 647 647 647 647 6 7 67  
9 T9 x( v, C% ~9 n" x7 U

3 t% A0 I5 s; J6 ?# j0 W765 765 765 765  65 6 5 635 635 635 635 635 635  35 3 5 325 325 32  3 2 302 302
: T) K6 D# R, f- _+ g3 l) h432 432 432  32 732 732 7 2 72  720 720 720  20 620 620 6 0 60  605 605 6 5 645
' l5 d; B3 y6 ?10  1 0  10 410 410 410 410 410 41  4 1  41 741 741 741 741 741 741 741 741 7 1

: G9 o+ Y  C9 ~4 X) D" e302 302 302 302 302 302  02 0 2 012 012 012
645 64  6 4 614 614  14 314 314 3 4 34  345
' h' L) d% I/ Q4 c+ C71  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