高手來試一下碎心拼圖遊戲？

mathe

修正了下移动允许规则，只需要32步了，看看是否正确

Cand 0
120
345
678

125
340
678

125
304
678

105
324
678

015
324
678

315
024
678

315
624
078

315
624
708

315
624
780

315
620
784

315
602
784

305
612
784

035
612
784

635
012
784

635
102
784

605
132
784

650
132
784

652
130
784

652
134
780

652
134
708

652
104
738

652
140
738

650
142
738

605
142
738

065
142
738

165
042
738

165
402
738

165
432
708

165
432
078

165
032
478

165
302
478

105
362
478

150
362
478

Cand 1
120
345
678

102
345
678

142
305
678

142
035
678

142
635
078

142
635
708

142
605
738

142
065
738

042
165
738

402
165
738

420
165
738

425
160
738

425
106
738

425
136
708

425
136
780

425
130
786

420
135
786

402
135
786

432
105
786

432
015
786

032
415
786

302
415
786

312
405
786

312
450
786

312
456
780

312
456
708

312
456
078

312
056
478

012
356
478

102
356
478

152
306
478

152
360
478

150
362
478

现在是否可以移动的判断规则如下:
对于一个横向移动的拼图:
i)拼图横向摆放，必然可以移动
ii)如果拼图不在中间一行，除非移动后目标列三个拼图都是纵向摆放，不然必然可以移动
iii) 如果拼图在中间一行而且纵向摆放，如果移动以后目标列不是三个拼图都是纵向摆放场景，那么起始列和目标列如果上面一排两个拼图排放方式相同或下面一排两个拼图摆放方式相同，就可以移动

而前面一个结果最后一个条件原先只判断了一半，所以丢失了一些情况

代码

ejsoon

mathe 发表于 2023-7-28 13:32
修正了下移动允许规则，只需要32步了，看看是否正确

Cand 0

試了cand0，可以。

這個「是否可移動判斷規則」很精彩，我正在研究…

王守恩

mathe 发表于 2023-7-28 13:32
修正了下移动允许规则，只需要32步了，看看是否正确

Cand 0

Cand 0 可以这样写：数字表示0所在的位置。
65214789,65214523,69856321,45874523。
1-1-11--,1-1-1-1-,11-1-1--,1-1-1-1-。

ejsoon

mathe 发表于 2023-7-27 22:18
那就需要提供更加进一步信息，每个方块长宽分别是多少。
由于总共状态只有9!种，每种状态最多有四种不同的 ...

那就需要提供更加进一步信息，每个方块长宽分别是多少。
由于总共状态只有9!种，每种状态最多有四种不同的转移方案，构成一个点的数目为9!,每个点的度数不超过4的图，然后计算其中两点的最短距离，这是典型的图论问题，计算不难。

華容道是否也可以用這種圖論的方法解開？

下方的頁面用的是廣度優先算法。我一開始也想用這個方法破解「碎心」。
http://simonsays-tw.com/web/Klotski/Klotski.html

ejsoon

mathe 发表于 2023-7-28 13:32
修正了下移动允许规则，只需要32步了，看看是否正确

Cand 0

我以為你是用甚麼數學軟件做的，想不到用的是cpp！

yuange1975

1998年就在海信电视上做了这个游戏。

随机打乱，怎么保证能玩出来？

懂群轮的就太简单，置换奇偶问题。或者参加或者接触过一些竞赛的就会接触到倒序这个概念，就很容易懂，倒序奇偶对应空块移动奇偶次。

所以如果随机款序排列后，检查一下奇偶，如果不对再随便交换一下不是空块的两个位置就行。


接近三十年前，我还出过一个类似的题，三阶魔方摔散，捡起来随机组合上，问能玩出来完全还原的概率？

如果真正知道理解了这个，魔方就不用记忆公式了。因为所有变换的关系都清楚了，任何最小变换
你都知道。然后所有的变换在你眼里都是线性关系，玩魔方就像解方程，就如多元线性方程组消元一样，一个个未知数就解出来了。

这个拼图也一样，只是拼图最小空间2*2太简单了。

ejsoon

yuange1975 发表于 2023-9-17 10:21
1998年就在海信电视上做了这个游戏。

随机打乱，怎么保证能玩出来？

三階魔方要隨機的話，只能靠擰。

摔碎再隨機拼，會有可能出現無解情況（我以前就遇過）

魔方只能靠公式，你也可以說你知道每個公式的變換關係，但沒有公式，你只知道每個面旋轉的結果而已。你也可以試試不靠公式，怎麼去「理解」，我看很難吧。

但拼圖（以及魔方的第一第二層）可以靠思維去完成。

還有就是，想不到這個可以用群論來解決。

yuange1975

魔方就是一个置换群。

三阶魔方的结构，六个面的中心骨架是固定的。8个顶点块之间可以互换，12个棱块之间可以互换。

三阶魔方最基本的动作是转一次90度角，所有的动作都是由基本动作构成。
转动90度，4个顶点块之间轮换就是3个置换，4个棱块之间轮换，也是3个置换。一次是6次置换属于总的是偶数个置换。

魔方摔散，随机装上去，这样顶点块和棱块可能置换位置必须同奇偶才是正确位置，就是奇偶1/2概率正确。

每个棱块有2面，是对称的2面都能装上，最小的旋转调整是2个棱块的2面都翻转。所以棱块的2面都安装正确的概率是1/2。

每个顶点块有3面，是对称的3面都能装上，最小的旋转调整是2个顶点块的2面都翻转总共3面，就是相当于最后有一个顶点块的面随机。所以顶点块的3面都安装正确的概率是1/3。

这样摔散的三阶魔方，随机安装上的概率就是1/2*1/2*1/3=1/12。

魔方随机安装上的状态数是：

8!*12!*2^12*3^8

而只有1/12的状态对应能玩出来，这样三阶魔方的真实状态数也就是魔方数
n=1/12*8!*12!*2^12*3^8=4.325*10^19。

4.3千亿亿，非常大的数字。

这么大的数字，看似很复杂，其实因为我们掌握了最小变换和最小变换空间，这些复杂关系都是线性了，就如解多元线性方程组的消元法一样，还原就如解方程组，一个个未知数就解出来了。

大一的时候接触到同寝室室友的三阶魔方，自己研究，基于高中就自学了的群论知识，很快就研究出来了以下的自己独创的还原方法。也有了那个摔散随机组合后能玩出来的概率题。



最小变换空间就是过同一顶点的三条棱，可以4个顶块两两置换，3个棱块轮换也就是2个置换。我的方法就是除了这3棱、先埃着还原别的，最后再还原这三条棱。这个置换棱块是3阶，顶块是2阶，所以同样的操作不同次数，就可以把棱块和顶块的置换独立出来了。

整个动作都是一个基本动作，所以不需要记忆公式。

这三条棱位置还原了后，最后就是棱上的面翻转。同样的都是基本动作，组合一下可以实现两条相交棱上的所有面都翻转，最后完成全部面都调整对。

这就是这套方法得到了最基本的任意置换，要解魔方根本没有难度。当然因为这个还原步骤每步不是最简的，速度肯定没有死记公式都是最简的结果那么快。
相当于我的是做乘法学会了方法，不用记忆什么都能按方法算出来，公式的就是最后一面的乘法都记忆下来了看到就直接上最简结果，肯定快了。

ejsoon

yuange1975 发表于 2023-9-19 13:01
魔方就是一个置换群。

三阶魔方的结构，六个面的中心骨架是固定的。8个顶点块之间可以互换，12个棱块之间 ...

可否用圖片、動畫或視頻，來介紹一下你的置換方法？

我是看不太懂。並且，你要置換三條棱上的塊，如何保證不影響其它塊？

ejsoon

https://www.52txr.cn/game/3DMF/index.html

這裏有一個3d魔方，你可以在手機或電腦上，開錄屏軟件，之後做成動畫視頻，來介紹你獨創的方法。