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

god

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

罗炳

请教

后面的数字是什么意思啊

fly_eager

很有兴趣！

god

765 765 765 7 5  75 475 475 475 475 4 5  45 145 145 145 145 1 5 15  153 153 153
1 H: e, x$ y( y) U3 E432 43  4 3 463 463  63 163 163 1 3 173 173  73 073 073 0 3 043 043 04  042 042
: d4 y! [, d+ e9 B- D10  102 102 102 102 102  02 0 2 062 062 062 062  62 6 2 672 672 672 672 67  6 7
* [- g8 F- {1 ~9 o
153 1 3 13  132 132 1 2  12 012 012 012 012
0 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  
$ ~) f5 G$ [* E4 }+ A2 R6 f4 p

6 _. r) i8 v0 S& r$ o$ N765 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

142 142 142 142 142 1 2  12 012 012 012 012
+ A' Q5 d1 e5 q  S  X057 057 057 05  0 5 045 045  45 345 345 345
; ^; o7 r5 E8 i* g 36 3 6 36  367 367 367 367 367  67 6 7 67  
/ G& N& J, Q$ L5 C
% {4 {' B* l$ Y% Z9 F* \
765 765 765 765  65 6 5 645 645 645 645 64  6 4 604 604 604 604  04 0 4 024 024
2 f9 v5 w( Z. U. M2 b  l432 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
" k9 }; f8 h: H2 `- _5 q
, R4 p  I, c% p, S) [- e024 024 02  0 2 012 012 012 012 012 012 012
615 61  614 614 6 4 634 634  34 3 4 34  345
3 A7 y1 S  K3 _* P8 B73  735 735 735 735 7 5  75 675 675 675 67  

" s) x4 i7 p6 U- ?3 w
765 765 765 765 765 765 765 7 5 75  753 753 753 753 7 3  73 173 173 173 173 1 3
" d1 C! S3 L) S2 \, b* a5 B  e! |432 43  4 3  43 143 143 1 3 163 163 16  162 162 1 2 152 152  52 052 052 0 2 072
; ?2 {) ~' n$ {6 }' ?& q10  102 102 102  02 0 2 042 042 042 042 04  0 4 064 064 064 064  64 6 4 654 654
2 s6 G" z( ?* M* k' A6 q: M2 m
5 i+ P: o& q4 `! K" a0 T7 _7 N$ P* `13  132 132 132 132 1 2  12 012 012 012 012
& [' z! Z- |& {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  

  x& A& r9 [+ k1 b. b& N
765 765 765 765 765 765 765 765 765 765 765 7 5  75 175 175 175 175 1 5 15  152
0 [; G1 d0 K1 b4 N; _432 43  4 3  43 143 143 1 3 13  132 132 1 2 162 162  62 062 062 0 2 072 072 07  
: w; _* {! ]. O3 v10  102 102 102  02 0 2 042 042 04  0 4 034 034 034 034  34 3 4 364 364 364 364

% U( [" B) v/ I5 q6 J5 K152 1 2  12 012 012 012 012 012 012 012 012
2 q3 |" t( Y. B0 7 057 057  57 357 357 357 35  3 5 345 345
- @* W  F  h* Q6 F% O# |; _364 364 364 364  64 6 4 64  647 647 6 7 67  
- K- |4 N0 Y, y6 F7 t5 m8 s6 o$ s6 P

# h* O* f( W! \, r) }765 765 765 7 5  75 475 475 475 475 4 5 45  452 452 4 2  42 142 142 142 142 142
1 h, L$ J. L3 A' J1 V432 432 4 2 462 462  62 162 162 1 2 172 172 17  1 7 157 157  57 357 357 357 35  
1 w& H6 ~1 v" r; ]7 M; r& h7 O10  1 0 130 130 130 130  30 3 0 360 360 360 360 360 360 360 360  60 6 0 60  607
+ o' O& r" p( ]" @9 |3 ?5 h# i8 q
% F: j. n' X8 {( O" h142 142 142 142 142 1 2  12 012 012 012 012
6 j% x$ _' A3 m/ h+ E* n, [* y3 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  
( a7 E, X! B* u/ e2 u; G

765 765 765 765  65 6 5 645 645 64  6 4 624 624 624 624 62  6 2 632 632 632 632
  l9 j# Q4 E2 m* P+ r/ m432 432 4 2  42 742 742 7 2 72  725 725 7 5 735 735 73  734 734 7 4 704 704  04
$ m8 t# H3 P% u+ u5 e! l2 Q10  1 0 130 130 130 130 130 130 130 130 130 1 0 10  105 105 105 105 1 5  15 715

1 _9 ~1 k, x" f+ U) y, k) x) [ 32 3 2 302 302 302 302  02 0 2 012 012 012
3 b' s- _6 G9 V4 u604 604 6 4 614 614  14 314 314 3 4 34  345
2 E# i' g7 _  j% M; M! l715 715 715 7 5  75 675 675 675 675 675 67  

; H) f4 {4 |* {3 M# C5 ?" @7 ~; O
765 765 765 765 765 765 765 765  65 6 5 625 625 62  6 2 602 602 602 602  02 0 2
* i0 d( o0 j/ s3 {- H432 432 4 2 42  420 420 420  20 720 720 7 0 70  705 705 7 5 715 715  15 615 615
  b" c3 r" I6 O( U; W10  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
2 }7 j( N$ r% F+ {+ @1 A743 7 3 73  735 735 7 5  75 675 675 675 67  

$ p6 @  T! g% N8 K+ c
. I# F5 ~" A$ X) @  U765 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

5 J! \& b! \% B/ W  ?7 _* o9 y32  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
8 V5 f9 [- K/ A( H417 417 417 4 7  47 647 647 647 647 6 7 67  
- d& P  Y6 f" n" N1 S
9 o9 ^4 u+ N6 Z0 O
. [5 |& k$ h4 |  G7 m765 765 765 765  65 6 5 635 635 635 635 635 635  35 3 5 325 325 32  3 2 302 302
2 d5 R  `+ P6 D9 z$ w3 o# x2 S432 432 432  32 732 732 7 2 72  720 720 720  20 620 620 6 0 60  605 605 6 5 645
$ y1 d2 a- f" i" M7 [8 x10  1 0  10 410 410 410 410 410 41  4 1  41 741 741 741 741 741 741 741 741 7 1
6 J& c6 v/ I/ z
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
2 L# p8 F" L% E$ O$ c0 {% T71  715 715 7 5  75 675 675 675 675 675 67