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

god

喜欢迎接挑战的请进来！ & n' b/ o' g" R3 x《小擂台》 这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所 5 i' H, |- R! z" t7 T以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于 我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 余生活，何况这个题目在今天研究，已经具有双重的考验作用了。 不要去找现成的答案。也不是那么好找。 一是完全用我们的大脑来解决问题，这个难度是有相当档次的。 ! F" }: D n7 [* ]3 Q' o 二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出 一个解决问题的搜索程序，解决这个问题。 ! @" Q8 E5 u4 `3 b 1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重 8 Y4 _( ]0 ~+ p/ G5 E- `排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下： ) ]5 V# C% x. B3 l. t. K在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格 / b D/ J" _0 l( P开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空 格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任 意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 + U7 W2 `3 \+ M) M0 d9 I为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步 # J3 D3 b% P% \9 M+ E: o6 o% C i以内完成就是智商很高的体现了。 , T2 _, [1 l3 N" P3 N' [7 q: J% R 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 x/ g+ n8 \% V- B! o 事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段 ——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小 时的计算机运算时间，才找到了全部的最优解。 2 A7 S( O- d7 _. Z% p5 m) } 他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能 ) h" d$ N2 ^$ I! _5 G3 X# i# U完成的。 , }9 B% g2 U; U 事实上，在20多年前当这个题目在国内公布之后，在短短的半年内， * e$ m* }) O! q f% J就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可 ( Y. Z( S. d& }0 j7 J! k能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然 是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 可能找到这十个最优解”的结论。 ( z5 B/ n l. r u, s8 d9 W 时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决 的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 6 J% c$ _+ w" P' T& E# |( C7 \) L) l可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就 找到这十个最优解，这都是可能的。 % I" t9 Q" q5 p0 f8 U3 t9 @ 科技的威力在解决此题与战胜SARS这件事上异曲同工。 % W% c6 l+ K4 r" {; P8 j 擂台已经摆下：请给出这十个最优解。 补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问. b) J$ W* K+ `8 Q( |2 v 加一下难度给个第二问: 证明:重排九宫最少步数为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
8 F& q3 M& @1 y432 43  4 3 463 463  63 163 163 1 3 173 173  73 073 073 0 3 043 043 04  042 042
$ z. M* X$ @# S( |' t5 j- V9 t10  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
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  


765 765 765 7 5  75 475 475 475 475 475 475 475 475 4 5 45  452 452 4 2  42 142
6 Q: ^  o  u# V. ?  F5 O2 s- c' }) y432 43  4 3 463 463  63 163 163 1 3 13  132 132 1 2 172 172 17  1 7 157 157  57
7 p3 K& X" a$ ?  H& M( }1 q- \10  102 102 102 102 102  02 0 2 062 062 06  0 6 036 036 036 036 036 036 036 036

8 n5 ~3 F4 k" H- C: e142 142 142 142 142 1 2  12 012 012 012 012
' L% I% v+ m2 Z057 057 057 05  0 5 045 045  45 345 345 345
" X* [5 J3 E4 H; C- l5 t 36 3 6 36  367 367 367 367 367  67 6 7 67  
. N  w$ Y# W7 N$ ^* G

765 765 765 765  65 6 5 645 645 645 645 64  6 4 604 604 604 604  04 0 4 024 024
1 U1 r& k; ~$ c: C+ S' K432 43  4 3  43 743 743 7 3 703 703 70  705 705 7 5 725 725  25 625 625 6 5 615
6 I/ e; r: g. {4 H2 t* }10  102 102 102 102 102 102 1 2 12  123 123 123 123 1 3  13 713 713 713 713 7 3

024 024 02  0 2 012 012 012 012 012 012 012
1 p8 `" f8 B# o0 h0 s. y615 61  614 614 6 4 634 634  34 3 4 34  345
, }& W9 L3 K9 F2 y* a4 h73  735 735 735 735 7 5  75 675 675 675 67  
6 T  m3 C' {# O8 e
7 k5 A  a  V0 o2 o* C
765 765 765 765 765 765 765 7 5 75  753 753 753 753 7 3  73 173 173 173 173 1 3
% Q  x- h( X# N7 b% D& [& s' n432 43  4 3  43 143 143 1 3 163 163 16  162 162 1 2 152 152  52 052 052 0 2 072
10  102 102 102  02 0 2 042 042 042 042 04  0 4 064 064 064 064  64 6 4 654 654
% @0 u2 U9 X* D) B7 {
0 S! ?% \+ z# e: S13  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  

9 x' ?: i5 [1 B9 b$ j
765 765 765 765 765 765 765 765 765 765 765 7 5  75 175 175 175 175 1 5 15  152
' s" X  o) x( S) a- \7 \% [/ O432 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
! x$ S( s/ s7 N$ I4 X
152 1 2  12 012 012 012 012 012 012 012 012
0 7 057 057  57 357 357 357 35  3 5 345 345
0 a+ k3 t8 Q* p2 Q# ~1 f9 n364 364 364 364  64 6 4 64  647 647 6 7 67  
8 B- }/ Z- X3 X3 S5 M$ I0 J, L8 p
' P! F7 s5 r  g4 U6 k
, k! Z, X  l- {, d- A: @8 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  
10  1 0 130 130 130 130  30 3 0 360 360 360 360 360 360 360 360  60 6 0 60  607

8 y6 H, A$ y) [+ i' L142 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  
5 Y9 R2 m3 t) a3 ?/ H$ H5 [6 e( J' u2 l
; E6 F% W7 v* q  W: a1 S( ?
* e  J" @+ o+ j# J765 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
10  1 0 130 130 130 130 130 130 130 130 130 1 0 10  105 105 105 105 1 5  15 715

6 S2 u1 e+ z& p# M- U; _: ~ 32 3 2 302 302 302 302  02 0 2 012 012 012
6 c8 K% G! l9 v9 I, i! W1 S604 604 6 4 614 614  14 314 314 3 4 34  345
" F1 P8 y& j; E( v# J/ S/ X715 715 715 7 5  75 675 675 675 675 675 67  
) D# W: F9 \* G9 l

, N" Y6 H, O& V) h! Z9 k$ E$ w765 765 765 765 765 765 765 765  65 6 5 625 625 62  6 2 602 602 602 602  02 0 2
0 {$ M9 m0 C6 {- U2 F432 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
/ z* z2 T1 Z6 S) R1 G$ l# U. s
0 r5 l. |7 d  r5 ], Z; n3 g012 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  

1 ]* l; ?1 e8 P' @, O& ~- r% J
* W& b, }/ D( l8 e* V765 765 765 765  65 6 5 635 635 635 635 635 635 635 635 635 635  35 3 5 325 325
" M- y1 b6 l; Y/ P, M432 432 432  32 732 732 7 2  72 472 472 4 2 42  420 420 420  20 620 620 6 0 60  
- t1 B& X  V9 W4 K% L3 X/ T10  1 0  10 410 410 410 410 410  10 1 0 170 170 17  1 7  17 417 417 417 417 417
2 _. I- I! @3 e1 E" ]  m* [% u
/ f" o- S# g5 R32  3 2 302 302 302 302  02 0 2 012 012 012
! w) x: }! b8 k605 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  
! ?* D! c5 B5 V" l( s1 \2 t

765 765 765 765  65 6 5 635 635 635 635 635 635  35 3 5 325 325 32  3 2 302 302
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

. ^5 p# W, X: Z302 302 302 302 302 302  02 0 2 012 012 012
& z  `: F! h4 H( p! s- ~* j+ V$ n645 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

很有兴趣！

罗炳

请教

后面的数字是什么意思啊