移动数字的问题

骰迷

798123456要多少步?

jx215

原帖由 lulijie 于 2009-2-8 21:29 发表
9个数字分布在9个格子总状态数为9的阶乘=362880种
  其中右下角为空格的总状态数为8的阶乘=40320种。
用(123456789) 表示以下状态              9代表空格。
        1 2 3
        4 5 6
        7 8 9
经过电 ...

这位老师用的是什么软件或者用什么语言编程的？

骰迷

還想請教一下：既然TONY說只有兩種類別的狀態，那麼大概可以分成12345678(9)與12345687(9)兩種原始狀態。請問12345678(9)的狀態數跟12345687(9)的狀態數是不是一樣？若是一樣，它們的總狀態數又是否等於　8!　？若是小於，那剩下來的幾種呢？它們兩個組別都不算了？還有第三種原始狀態麼？

lulijie

(798123456) 21步。
我用的是VB 6.0编程。
我昨天使用另一种编码，算出的结果还是一样。
现在使用第三种编码再算，如果还是一样，我就接受这个结果了。

tonylmd

tony只是引用哈
两位也可将最终结论编辑入百度百科中呀

骰迷

我搞不懂了。
123
456
789
你旋轉看看，就變成這樣了：
987
654
321
所以說呢，這兩種次序基本是沒有分別的嘛。把順序的最遠狀態
654
321
897
旋轉過來：
798
123
456
移動的步數也是一樣的吧。請lulijie搞出798123456的二十一步，和654321897的二十九步中每一步弄出來，比對參照一下。

lulijie

原因找到了，范了一个很简单的错误，不是程序设计的问题，而是没把最后两步的结果记录下来。
程序设计的思想是：用3个变量保存数据。
JieGuo1   保存N步的已经扩展过的所有状态，
JieGuo0  保存N-1步的所有状态，
JieGuo   保存N步的未经扩展的所有状态和新增加的N+1步的状态。
处理N步的状态时，新增加的状态根据9在位置上的不同，可增加的新状态数为2 、3、 4个。
检查增加的新状态是否已经出现过，只要检查在JieGuo0 和 JieGuo中是否已经出现即可。（增加的N+1步新状态，前面出现过的只能出现在N-1步的状态中）
当N增加时，把JieGuo0  记到文件中，JieGuo1移到JieGuo0中。
程序结束时，却忘记把最后的JieGuo0  和JieGuo1，记录下来。
-------------------------------------------------------------------------------------
最终结果如下：
最少步数N         总状态数      右下角为空格的总状态数
           0                            1                        1
           1                            2                        0
           2                            4                        0
           3                            8                        0
           4                           16                       2               
           5                           20                       0
           6                           39                       8
           7                           62                       0
           8                         116                     26
           9                         152                       0
          10                        286                     48
          11                        396                       0
          12                        748                   138
          13                      1024                       0
          14                      1893                   364
          15                      2512                       0
          16                      4485                   834
          17                      5638                       0
          18                      9529                 1852
          19                    10878                       0
          20                    16993                 3337
          21                    17110                       0
          22                    23952                 4738
          23                    20224                       0
          24                    24047                 4904
          25                    15578                       0
          26                    14560                 3009
          27                      6274                       0           
          28                      3910                   854
          29                        760                       0
          30                        221                     45
          31                          2                       0
         总计                181440               20160
-----------------------------------------------------------------------
最远的状态为31步，只有2个，（647859321）和（867254391）。
右下角为空格的最远状态为30步，（347682519）是其中之一。

lulijie

798123456最少移动步数21，具体如下：
7  8
123
456
  ↓
728
1  3
456
  ↓
728
153
4  6
  ↓
728
153
  46
  ↓
728
  53
146
  ↓
  28
753
146
  ↓
2  8
753
146
  ↓
28  
753
146
  ↓
283
75  
146
  ↓
283
7  5
146
  ↓
283
  75
146
  ↓
283
175
  46
  ↓
283
175
4  6
  ↓
283
1  5
476
  ↓
2  3
185
476
  ↓
  23
185
476
  ↓
123
  85
476
  ↓
123
485
  76
  ↓
123
485
7  6
  ↓
123
4  5
786
  ↓
123
45  
786
  ↓
123
456
78  
-----------------------------------------------------------
654321897最少移动步数29，具体如下：
654
321
8  7
  ↓
654
3  1
827
  ↓
6  4
351
827
  ↓
  64
351
827
  ↓
364
  51
827
  ↓
364
5  1
827
  ↓
364
51  
827
  ↓
364
517
82  
  ↓
364
517
8  2
  ↓
364
517
  82
  ↓
364
  17
582
  ↓
364
1  7
582
  ↓
364
17  
582
  ↓
36  
174
582
  ↓
3  6
174
582
  ↓
  36
174
582
  ↓
136
  74
582
  ↓
136
7  4
582
  ↓
136
74  
582
  ↓
136
742
58  
  ↓
136
742
5  8
  ↓
136
742
  58
  ↓
136
  42
758
  ↓
136
4  2
758
  ↓
136
42  
758
  ↓
13  
426
758
  ↓
1  3
426
758
  ↓
123
4  6
758
  ↓
123
456
7  8
  ↓
123
456
78  
------------------------
最远状态647859321，最少移动步数31，具体如下：
647
85  
321
  ↓
64  
857
321
  ↓
6  4
857
321
  ↓
654
8  7
321
  ↓
654
  87
321
  ↓
654
387
  21
  ↓
654
387
2  1
  ↓
654
3  7
281
  ↓
654
37  
281
  ↓
654
371
28  
  ↓
654
371
2  8
  ↓
654
3  1
278
  ↓
6  4
351
278
  ↓
  64
351
278
  ↓
364
  51
278
  ↓
364
251
  78
  ↓
364
251
7  8
  ↓
364
2  1
758
  ↓
364
21  
758
  ↓
36  
214
758
  ↓
3  6
214
758
  ↓
  36
214
758
  ↓
236
  14
758
  ↓
236
1  4
758
  ↓
236
14  
758
  ↓
23  
146
758
  ↓
2  3
146
758
  ↓
  23
146
758
  ↓
123
  46
758
  ↓
123
4  6
758
  ↓
123
456
7  8
  ↓
123
456
78  
---------------------------------------------------
最远状态之二867254391，最少移动步数31，具体如下：
867
254
3  1
  ↓
867
2  4
351
  ↓
8  7
264
351
  ↓
  87
264
351
  ↓
287
  64
351
  ↓
287
364
  51
  ↓
287
364
5  1
  ↓
287
364
51  
  ↓
287
36  
514
  ↓
28  
367
514
  ↓
2  8
367
514
  ↓
268
3  7
514
  ↓
268
  37
514
  ↓
268
537
  14
  ↓
268
537
1  4
  ↓
268
537
14  
  ↓
268
53  
147
  ↓
26  
538
147
  ↓
2  6
538
147
  ↓
236
5  8
147
  ↓
236
  58
147
  ↓
236
158
  47
  ↓
236
158
4  7
  ↓
236
158
47  
  ↓
236
15  
478
  ↓
23  
156
478
  ↓
2  3
156
478
  ↓
  23
156
478
  ↓
123
  56
478
  ↓
123
456
  78
  ↓
123
456
7  8
  ↓
123
456
78

lulijie

下面是九宫数字的解答程序，输入任何一种状态，空格用9代替，运行后就会给出具体移动步骤。若程序不能运行，可能与缺少VB运行环境有关。
   九宫移动解法.part01.rar (250 KB, 下载次数: 0)

2009-2-10 22:23:12 上传

下载次数: 0
九宫移动解法part01

   九宫移动解法.part02.rar (250 KB, 下载次数: 0)

2009-2-10 22:23:12 上传

下载次数: 0
九宫移动解法part02

   九宫移动解法.part03.rar (246.31 KB, 下载次数: 0)

2009-2-10 22:23:12 上传

下载次数: 0
九宫移动解法part03

lulijie

若程序不能运行，可能与组件没有注册有关，试试以下程序。不适用于win98系统。
       组件注册.rar (186 Bytes, 下载次数: 0)

2009-2-10 22:38:57 上传

下载次数: 0