[灌水]喜欢迎接挑战的请进来！

god

喜欢迎接挑战的请进来！ 《小擂台》 这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所 1 ~8 ]+ B. o8 |以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于 我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 - H" ~) o7 W$ R2 Z$ h, W余生活，何况这个题目在今天研究，已经具有双重的考验作用了。 K9 {& ?4 g% K: L l0 w3 G+ D2 V 不要去找现成的答案。也不是那么好找。 - I+ [0 d, r* F) v3 \, @ 一是完全用我们的大脑来解决问题，这个难度是有相当档次的。 二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出 一个解决问题的搜索程序，解决这个问题。 1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重 排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下： 在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格 $ _8 {9 s6 R& G& p( w! R+ t开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空 2 u' h+ V. Z% ]3 V. m1 N' C z格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任 意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 # D- G! O; c- U& H' ?; h- b6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 / [0 \ A; I* c; a/ f为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步 2 I! s/ B# J9 T; D以内完成就是智商很高的体现了。 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段 ——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小 ; ^2 b# y9 a+ K9 J# p6 m1 O$ |* `时的计算机运算时间，才找到了全部的最优解。 & `! A3 e% _0 c 他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能 4 _5 C* @8 Y b! Q6 b- l完成的。 / D, ^; _, G" f- o2 e3 S2 c 事实上，在20多年前当这个题目在国内公布之后，在短短的半年内， f N+ Z: z. B+ P8 N$ X* u# h就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可 / `; f% \, q6 N( h1 H R能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然 ; _3 ^0 S0 \# Z( O是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 , S& `& C5 J' T# |, p可能找到这十个最优解”的结论。 + B0 J! x' `/ l+ c6 t+ n 时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决 ' ?/ n- Q% K4 Z, R% n( S的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 - p1 Z' s* a/ I8 h6 Q可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就 4 }' l, T0 }6 o' u( S找到这十个最优解，这都是可能的。 * w# i3 ^1 b. E3 V) a* o 科技的威力在解决此题与战胜SARS这件事上异曲同工。 ) R, ~6 P- d$ J* B+ ^0 n 擂台已经摆下：请给出这十个最优解。 $ `, U& A( F1 k' J ^补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问. 0 z; K# N8 X# D- j& F3 S& P! P g 加一下难度给个第二问: 证明:重排九宫最少步数为30步,并且只有十个最优解

god

765 765 765 7 5  75 475 475 475 475 4 5  45 145 145 145 145 1 5 15  153 153 153
5 ?1 l  k& L* M" n( e432 43  4 3 463 463  63 163 163 1 3 173 173  73 073 073 0 3 043 043 04  042 042
; U6 j. v8 d/ B10  102 102 102 102 102  02 0 2 062 062 062 062  62 6 2 672 672 672 672 67  6 7

" M0 I5 }7 m2 {% ?9 Z153 1 3 13  132 132 1 2  12 012 012 012 012
  ]; f" {5 ]# R- [* I0 2 052 052 05  0 5 035 035  35 3 5 345 345
647 647 647 647 647 647 647 647 647 6 7 67  

$ g: y' R" K% A& T4 E
765 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
9 R! ~: V! A9 I  r+ _2 ?$ Z10  102 102 102 102 102  02 0 2 062 062 06  0 6 036 036 036 036 036 036 036 036

142 142 142 142 142 1 2  12 012 012 012 012
057 057 057 05  0 5 045 045  45 345 345 345
9 {2 X; s4 B# E( X7 t) h. X" a& R 36 3 6 36  367 367 367 367 367  67 6 7 67  

! H4 j6 ^1 c+ i1 m; a2 z  w
765 765 765 765  65 6 5 645 645 645 645 64  6 4 604 604 604 604  04 0 4 024 024
432 43  4 3  43 743 743 7 3 703 703 70  705 705 7 5 725 725  25 625 625 6 5 615
2 N6 H# ?' d- ^/ S7 P9 ~# H9 \5 {10  102 102 102 102 102 102 1 2 12  123 123 123 123 1 3  13 713 713 713 713 7 3
, l; Z4 O  A0 R; ?5 w- _: c+ n
, M: [3 x* _0 \: ]0 X024 024 02  0 2 012 012 012 012 012 012 012
( h: J+ e1 S0 y9 I1 D615 61  614 614 6 4 634 634  34 3 4 34  345
73  735 735 735 735 7 5  75 675 675 675 67  
4 \) b2 D# B$ ~0 N: D' M

' A4 e0 r- Y9 E3 z- T: i; V8 y765 765 765 765 765 765 765 7 5 75  753 753 753 753 7 3  73 173 173 173 173 1 3
2 D0 H, k/ J1 r1 t6 Y8 L; B# S* q432 43  4 3  43 143 143 1 3 163 163 16  162 162 1 2 152 152  52 052 052 0 2 072
* r& R' h6 Q4 h5 J  j& \9 b10  102 102 102  02 0 2 042 042 042 042 04  0 4 064 064 064 064  64 6 4 654 654

! c4 x; U  i3 ]; E2 N6 f13  132 132 132 132 1 2  12 012 012 012 012
072 07  074 074 0 4 034 034  34 3 4 34  345
654 654 65  6 5 675 675 675 675 675 675 67  

+ Z# P5 L/ q9 R
0 b8 k1 H3 Q* j: R6 M% |9 q4 o! k* |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  
10  102 102 102  02 0 2 042 042 04  0 4 034 034 034 034  34 3 4 364 364 364 364
3 {8 B! Q% E- B4 D% k
152 1 2  12 012 012 012 012 012 012 012 012
3 \! N( G6 Z% }- t) ~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  


5 O: e  x% O- A8 g+ o. z765 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  
! H, q! _$ p5 W7 i9 m' a8 p7 o) ^10  1 0 130 130 130 130  30 3 0 360 360 360 360 360 360 360 360  60 6 0 60  607

142 142 142 142 142 1 2  12 012 012 012 012
3 5 305 305  05 0 5 045 045  45 345 345 345
1 |& P2 v) g; C- Y5 q/ |607 6 7  67 367 367 367 367 367  67 6 7 67  
4 G  X7 D9 g6 Y/ B
6 E6 k% T8 ]6 ?  R3 N* C( M! \$ @
1 W3 E1 U+ V# Q1 ~3 q& w1 A( ^765 765 765 765  65 6 5 645 645 64  6 4 624 624 624 624 62  6 2 632 632 632 632
2 c- q, J5 h' J" B/ s432 432 4 2  42 742 742 7 2 72  725 725 7 5 735 735 73  734 734 7 4 704 704  04
10  1 0 130 130 130 130 130 130 130 130 130 1 0 10  105 105 105 105 1 5  15 715
; N/ T7 Z0 p( w+ }2 `3 a
32 3 2 302 302 302 302  02 0 2 012 012 012
, N  h$ Z+ p# f, k( Z604 604 6 4 614 614  14 314 314 3 4 34  345
( p/ z" a) R4 L8 _4 D" H715 715 715 7 5  75 675 675 675 675 675 67  
9 u1 Y: l7 y7 {2 `/ `  @' P
! s* k! ]! I/ X# Q, d0 b
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
, w7 w& V1 V/ @* p9 K10  1 0 130 130 13  1 3  13 413 413 413 413 413 413 413 413 4 3  43 743 743 743

012 012 012 012 012 012 012 012 012 012 012
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  

" d  l5 }+ ~) X& W0 b' d; l$ r
/ z: L/ q( J; N* i$ `2 W765 765 765 765  65 6 5 635 635 635 635 635 635 635 635 635 635  35 3 5 325 325
5 x0 _  b5 E* s3 d6 X9 ]432 432 432  32 732 732 7 2  72 472 472 4 2 42  420 420 420  20 620 620 6 0 60  
+ P* M, s' B& }4 T10  1 0  10 410 410 410 410 410  10 1 0 170 170 17  1 7  17 417 417 417 417 417
! m% x5 c5 g0 H" y* h6 D
- y) A% W0 Z# Q( q  ?32  3 2 302 302 302 302  02 0 2 012 012 012
) D5 C  _# t" t; X; \) u  z605 605 6 5 615 615  15 315 315 3 5 345 345
4 N: p* k( P$ p0 _417 417 417 4 7  47 647 647 647 647 6 7 67  
+ @  `1 V6 a7 S  W- L. w% G# u

765 765 765 765  65 6 5 635 635 635 635 635 635  35 3 5 325 325 32  3 2 302 302
, Y9 Q, n% U7 m! p% ?432 432 432  32 732 732 7 2 72  720 720 720  20 620 620 6 0 60  605 605 6 5 645
10  1 0  10 410 410 410 410 410 41  4 1  41 741 741 741 741 741 741 741 741 7 1
& n# h3 [" ^: Y8 R+ t# D. ~! f
302 302 302 302 302 302  02 0 2 012 012 012
645 64  6 4 614 614  14 314 314 3 4 34  345
71  715 715 7 5  75 675 675 675 675 675 67

fly_eager

很有兴趣！

罗炳

请教

后面的数字是什么意思啊