数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 难题征解 › 移动滑块的趣味难题
返回列表 发新帖
查看: 582|回复: 13

[悬赏] 移动滑块的趣味难题

[复制链接]
iseemu2009
发表于 2025-2-26 00:22:32 | 显示全部楼层 |阅读模式
购买主题 已有 1 人购买  本主题需向作者支付 1 枚金币 才能浏览
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

mathe
发表于 2025-2-26 08:09:54 来自手机 | 显示全部楼层
这个题目由于限制棋盘为6*6，其状态数为36*35!/(17!*18!)约等于163G个状态的最短路径问题，如果考虑旋转和翻转对称，可以再除以8，状态还是太多了的。
不过这个问题我们可以采用双向搜索，由于sqrt(163G)才0.4M,我们可以分别从起始和结束状态开始做广度优先搜索，记录所有中间状态，直到双方相遇。从概率上来说，数据量在M基本就会相遇了(生日悖论)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

iseemu2009
 楼主| 发表于 2025-2-26 10:10:09 来自手机 | 显示全部楼层
那试算一下4x4的盘面，初始状态和状态二都取图中左上部分4x4区域。其它不变
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

hujunhua
发表于 2025-2-26 10:31:12 | 显示全部楼层
状态数不能除以8，（旋转,反射）对称的两个状态不等价。因为从一个状态到另一个状态只能通过移动滑块，不能旋转、翻转棋盘。
把这些滑块在初始状态逐列从上到下编号1~15，任一状态都视为按此位置顺序的一个排列σ，那么每个状态都可赋一个逆序值τ(σ)。
滑块上下滑动不改变逆序值，左右滑动会改变6个，Δτ=±1±1±1±1±1±1≡0(mod2), 所以只有逆序值为偶数的状态才是可达的。

如果无视编号，只看颜色的话，同一个二色状态包括17!·18!个排列，其中奇偶各半，因为交换任何两个号块，奇偶改变。
所以任一个二色状态都包含可达排列，故都是可达的。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

iseemu2009
 楼主| 发表于 2025-2-26 19:04:06 | 显示全部楼层
由于原题目中给出的数据有些大，计算量惊人，不便于思考和分析，我把相关数据作了一些精简，请大家重新考虑这个问题。
移动滑块难题.png
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-2-27 08:53:34 | 显示全部楼层
4*4计算量很小，最少28步，体力值最小126
  1. score:0
  2. *011
  3. 0011
  4. 0011
  5. 0011
  6. score:4
  7. 0*11
  8. 0011
  9. 0011
  10. 0011
  11. score:7
  12. 0011
  13. 0*11
  14. 0011
  15. 0011
  16. score:11
  17. 0011
  18. 01*1
  19. 0011
  20. 0011
  21. score:17
  22. 00*1
  23. 0111
  24. 0011
  25. 0011
  26. score:22
  27. 0*01
  28. 0111
  29. 0011
  30. 0011
  31. score:27
  32. *001
  33. 0111
  34. 0011
  35. 0011
  36. score:30
  37. 0001
  38. *111
  39. 0011
  40. 0011
  41. score:34
  42. 0001
  43. 1*11
  44. 0011
  45. 0011
  46. score:37
  47. 0001
  48. 1011
  49. 0*11
  50. 0011
  51. score:40
  52. 0001
  53. 1011
  54. 0011
  55. 0*11
  56. score:44
  57. 0001
  58. 1011
  59. 0011
  60. 01*1
  61. score:50
  62. 0001
  63. 1011
  64. 00*1
  65. 0111
  66. score:55
  67. 0001
  68. 1011
  69. 0*01
  70. 0111
  71. score:60
  72. 0001
  73. 1011
  74. *001
  75. 0111
  76. score:63
  77. 0001
  78. 1011
  79. 0001
  80. *111
  81. score:67
  82. 0001
  83. 1011
  84. 0001
  85. 1*11
  86. score:71
  87. 0001
  88. 1011
  89. 0001
  90. 11*1
  91. score:75
  92. 0001
  93. 1011
  94. 0001
  95. 111*
  96. score:81
  97. 0001
  98. 1011
  99. 000*
  100. 1111
  101. score:86
  102. 0001
  103. 1011
  104. 00*0
  105. 1111
  106. score:91
  107. 0001
  108. 1011
  109. 0*00
  110. 1111
  111. score:97
  112. 0001
  113. 1*11
  114. 0000
  115. 1111
  116. score:101
  117. 0001
  118. 11*1
  119. 0000
  120. 1111
  121. score:105
  122. 0001
  123. 111*
  124. 0000
  125. 1111
  126. score:111
  127. 000*
  128. 1111
  129. 0000
  130. 1111
  131. score:116
  132. 00*0
  133. 1111
  134. 0000
  135. 1111
  136. score:121
  137. 0*00
  138. 1111
  139. 0000
  140. 1111
  141. score:126
  142. *000
  143. 1111
  144. 0000
  145. 1111
复制代码

点评

mathe
我设置时作成空格在移动了，也就是分数和你的左右上下颠倒了  发表于 2025-2-27 13:13
iseemu2009
第一步score=0，表示初始态是正确的，但第6步score=4是不是设置错了？因为第一行的0向左移动了一格，score=5才对。  发表于 2025-2-27 12:36
mathe
我结束状态设错了，我前面弄成16格顺序变色了，原来换列时保持同色  发表于 2025-2-27 11:38
iseemu2009
第142步至完成，完成状态和要求的不一致啊，不是应该0，1交叉排列吗？  发表于 2025-2-27 11:05
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2025-2-27 13:26:47 | 显示全部楼层
  1. score:0
  2. *011
  3. 0011
  4. 0011
  5. 0011
  6. score:5
  7. 0*11
  8. 0011
  9. 0011
  10. 0011
  11. score:10
  12. 01*1
  13. 0011
  14. 0011
  15. 0011
  16. score:16
  17. 0111
  18. 00*1
  19. 0011
  20. 0011
  21. score:20
  22. 0111
  23. 0*01
  24. 0011
  25. 0011
  26. score:24
  27. 0111
  28. *001
  29. 0011
  30. 0011
  31. score:27
  32. *111
  33. 0001
  34. 0011
  35. 0011
  36. score:32
  37. 1*11
  38. 0001
  39. 0011
  40. 0011
  41. score:37
  42. 11*1
  43. 0001
  44. 0011
  45. 0011
  46. score:42
  47. 111*
  48. 0001
  49. 0011
  50. 0011
  51. score:48
  52. 1111
  53. 000*
  54. 0011
  55. 0011
  56. score:52
  57. 1111
  58. 00*0
  59. 0011
  60. 0011
  61. score:56
  62. 1111
  63. 0*00
  64. 0011
  65. 0011
  66. score:59
  67. 1*11
  68. 0100
  69. 0011
  70. 0011
  71. score:64
  72. 11*1
  73. 0100
  74. 0011
  75. 0011
  76. score:70
  77. 1101
  78. 01*0
  79. 0011
  80. 0011
  81. score:76
  82. 1101
  83. 0110
  84. 00*1
  85. 0011
  86. score:80
  87. 1101
  88. 0110
  89. 0*01
  90. 0011
  91. score:86
  92. 1101
  93. 0110
  94. 0001
  95. 0*11
  96. score:91
  97. 1101
  98. 0110
  99. 0001
  100. 01*1
  101. score:94
  102. 1101
  103. 0110
  104. 00*1
  105. 0101
  106. score:99
  107. 1101
  108. 0110
  109. 001*
  110. 0101
  111. score:105
  112. 1101
  113. 0110
  114. 0011
  115. 010*
  116. score:109
  117. 1101
  118. 0110
  119. 0011
  120. 01*0
  121. score:112
  122. 1101
  123. 0110
  124. 00*1
  125. 0110
  126. score:116
  127. 1101
  128. 0110
  129. 0*01
  130. 0110
  131. score:120
  132. 1101
  133. 0110
  134. *001
  135. 0110
  136. score:126
  137. 1101
  138. 0110
  139. 0001
  140. *110
  141. score:131
  142. 1101
  143. 0110
  144. 0001
  145. 1*10
  146. score:134
  147. 1101
  148. 0110
  149. 0*01
  150. 1010
  151. score:137
  152. 1101
  153. 0*10
  154. 0101
  155. 1010
  156. score:141
  157. 1101
  158. *010
  159. 0101
  160. 1010
  161. score:144
  162. *101
  163. 1010
  164. 0101
  165. 1010
复制代码

点评

mathe
前面28次终止状态不同。这个32次最少  发表于 2025-2-27 14:20
iseemu2009
另一个方面，你的程度似乎没解决：有的路线要28次，但耗体力值155；有的要34次，但体力值139（数据为举例）。现要在众多方案里直接搜索体力值最小值是多少，不管方案的次数。   发表于 2025-2-27 14:17
iseemu2009
现在这解答过程应该没错了，很棒的构思。根据代码编行数计算，共移动了（161-1）/5=32次，耗体力值144。但这是众多路线中的一条，还是已经证明了是次数最少的路线？   发表于 2025-2-27 14:15
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-5-9 14:20 , Processed in 0.041232 second(s), 23 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表