里面分别是1-8,8个数字，剩下一个空位，一个可行步骤指的是:把空位相邻的一个数字挪到空位里，同时这个数字原位置成为空位
e.g.
1 2 3 1 3
4 6 -> 4 2 6
7 5 8 7 8 9
最终目标:
把棋盘排成
1 2 3
4 5 6
7 8
棋盘的inverse是棋子排列的一个属性，理解为按照排拉成一个1x9的行，然后前面数字大于后面数字的pair数量:
e.g.
1 2 3 4 5 6 7 8 => inverse = 0
8 7 6 5 4 3 2 1 => inverse = 28
并非所有棋盘配置都可解:
e.g. (unsolvable)
1 2 3
4 5 6
8 7
问题:
1. (easy) 如果一个初始棋盘配置为可解的，那么其inverse必须为偶数
2. (medium)如果一个棋盘配置的inverse为偶数，则此配置可解
3x3的棋盘
版主： verdelite， TheMatrix
Re: 3x3的棋盘
Python党觉得这题可以穷举。（ヅ） 写了： 2023年 2月 9日 14:42 里面分别是1-8,8个数字，剩下一个空位，一个可行步骤指的是:把空位相邻的一个数字挪到空位里，同时这个数字原位置成为空位
e.g.
1 2 3 1 3
4 6 -> 4 2 6
7 5 8 7 8 9
最终目标:
把棋盘排成
1 2 3
4 5 6
7 8
棋盘的inverse是棋子排列的一个属性，理解为按照排拉成一个1x9的行，然后前面数字大于后面数字的pair数量:
e.g.
1 2 3 4 5 6 7 8 => inverse = 0
8 7 6 5 4 3 2 1 => inverse = 28
并非所有棋盘配置都可解:
e.g. (unsolvable)
1 2 3
4 5 6
8 7
问题:
1. (easy) 如果一个初始棋盘配置为可解的，那么其inverse必须为偶数
2. (medium)如果一个棋盘配置的inverse为偶数，则此配置可解
Re: 3x3的棋盘
只考虑I值不为0的情况
从单行序看，每次相对不动或者让其中1个向前或向后移动2个位置
不失本质，只考虑移动2位的情况
1.
反向/逆时推而“复盘”
每次操作是
abc 变
1_1. bca
ab ac bc比较变
ba ca bc
奇偶性不变
1_2. cab
类似
奇偶性不变
2.
把8移到最后
2_1.一直到尾部
821类型
I值减2
2_2
最后一步可能会是
182或281
参见1中奇偶性不变的讨论
问题就转化成了size 7的问题。如此下去。。。
从单行序看，每次相对不动或者让其中1个向前或向后移动2个位置
不失本质，只考虑移动2位的情况
1.
反向/逆时推而“复盘”
每次操作是
abc 变
1_1. bca
ab ac bc比较变
ba ca bc
奇偶性不变
1_2. cab
类似
奇偶性不变
2.
把8移到最后
2_1.一直到尾部
821类型
I值减2
2_2
最后一步可能会是
182或281
参见1中奇偶性不变的讨论
问题就转化成了size 7的问题。如此下去。。。
Re: 3x3的棋盘
我那样做不也做出来了吗？为啥非要用不变量（如果有，就是之前说的：I的奇偶性不会因做了任何可允许操作而变吧？）？
原问题是（I，8）
(I,8)按第2部分的做法，（如有需要必能做些准备后把8向后移动直到移动到最后）等价简化成（I-偶数，7）
（上述做法可用，只是叙述同样稍微有点啰嗦）。。。
最终就是（I-偶数=0或1，3）
也就是：
123 （若I为偶）
或
213 （若I为奇）
因此，I是偶数与可解性完全等同。
原题两部分这样都被证明了。
原问题是（I，8）
(I,8)按第2部分的做法，（如有需要必能做些准备后把8向后移动直到移动到最后）等价简化成（I-偶数，7）
（上述做法可用，只是叙述同样稍微有点啰嗦）。。。
最终就是（I-偶数=0或1，3）
也就是：
123 （若I为偶）
或
213 （若I为奇）
因此，I是偶数与可解性完全等同。
原题两部分这样都被证明了。
Re: 3x3的棋盘
我看过（我小孩玩过）这种常见的游戏板/”电子板“。最简单的是3x3，但我家里也有4x4（或者更高）的。
如果是4x4或其它n。应该也探求一下。
考虑前/后移动3位。
abcd
变
bcda或dabc
考虑前种：
ab ac ad bc bd cd
ba ca da bc bd cd
每次操作都改变了奇偶性。因此结论不成立了。
那个结论对
偶数n x 偶数n
的游戏板不成立，而对
奇数x奇数
情况成立
如果是4x4或其它n。应该也探求一下。
考虑前/后移动3位。
abcd
变
bcda或dabc
考虑前种：
ab ac ad bc bd cd
ba ca da bc bd cd
每次操作都改变了奇偶性。因此结论不成立了。
那个结论对
偶数n x 偶数n
的游戏板不成立，而对
奇数x奇数
情况成立
Re: 3x3的棋盘
meiyoumajia 写了： 2023年 2月 9日 22:46 我那样做不也做出来了吗？为啥非要用不变量（如果有，就是之前说的：I的奇偶性不会因做了任何可允许操作而变吧？）？
原问题是（I，8）
(I,8)按第2部分的做法，（如有需要必能做些准备后把8向后移动直到移动到最后）等价简化成（I-偶数，7）
（上述做法可用，只是叙述同样稍微有点啰嗦）。。。
最终就是（I-偶数=0或1，3）
也就是：
123 （若I为偶）
或
213 （若I为奇）
因此，I是偶数与可解性完全等同。
原题两部分这样都被证明了。
主要是我没怎么看懂你在说什么
我明天再读一读
Re: 3x3的棋盘
吹毛求疵挑毛病的话，你的第一个例子（我在引用里给加粗了）没写清楚，我应该是大概看懂题意了。（ヅ） 写了： 2023年 2月 9日 14:42 里面分别是1-8,8个数字，剩下一个空位，一个可行步骤指的是:把空位相邻的一个数字挪到空位里，同时这个数字原位置成为空位
e.g.
1 2 3 1 3
4 6 -> 4 2 6
7 5 8 7 8 9
最终目标:
把棋盘排成
1 2 3
4 5 6
7 8
棋盘的inverse是棋子排列的一个属性，理解为按照排拉成一个1x9的行，然后前面数字大于后面数字的pair数量:
e.g.
1 2 3 4 5 6 7 8 => inverse = 0
8 7 6 5 4 3 2 1 => inverse = 28
并非所有棋盘配置都可解:
e.g. (unsolvable)
1 2 3
4 5 6
8 7
问题:
1. (easy) 如果一个初始棋盘配置为可解的，那么其inverse必须为偶数
2. (medium)如果一个棋盘配置的inverse为偶数，则此配置可解
持仓抄底锁利，你钱你定
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
Re: 3x3的棋盘
对原题，也就是3x3，我时有具体的办法把8到3一个个放到最终的位置。如果要考虑有效办法/“算法”，对每个的做法有时会有些不同。
如果也要考虑更大的n，比如5x5，但不考虑算法/解决问题方法的有效程度，而只考虑数学问题，那就可以按下面的做法一步步退化/约化。
只考虑需要被处理的情况
对3x3：
如果要处理的数a不在最终安置位（8，7和6等被依次紧密放在最下方，从最右下角开始），
0。如果a在角上，把a-1或者以下一个放在中央，转整个外圈1次（7个操作，造成a离开了角），把中央数字填到空位
把a放在中央
把a放在a+1前（有时，也要做上面那种对外圈的针对“0。”情况的外圈反转/转，更多的转和部分转）
这样就能约化1步
此法可用于5x5等奇数边长的情况。从外圈做起，“中央”是3x3，复杂不少，要把a先放在中央3x3的外圈。在5x5的外圈完全定好最终位后，就是3x3定位的问题了。最后看它的开始两个数是否顺序/逆序。
如果也要考虑更大的n，比如5x5，但不考虑算法/解决问题方法的有效程度，而只考虑数学问题，那就可以按下面的做法一步步退化/约化。
只考虑需要被处理的情况
对3x3：
如果要处理的数a不在最终安置位（8，7和6等被依次紧密放在最下方，从最右下角开始），
0。如果a在角上，把a-1或者以下一个放在中央，转整个外圈1次（7个操作，造成a离开了角），把中央数字填到空位
把a放在中央
把a放在a+1前（有时，也要做上面那种对外圈的针对“0。”情况的外圈反转/转，更多的转和部分转）
这样就能约化1步
此法可用于5x5等奇数边长的情况。从外圈做起，“中央”是3x3，复杂不少，要把a先放在中央3x3的外圈。在5x5的外圈完全定好最终位后，就是3x3定位的问题了。最后看它的开始两个数是否顺序/逆序。
上次由 meiyoumajia 在 2023年 2月 10日 12:46 修改。
-
TheMatrix
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动： 275
- 帖子： 13574
- 注册时间： 2022年 7月 26日 00:35
Re: 3x3的棋盘
中国有个《华容道》游戏，好像也是这样的。meiyoumajia 写了： 2023年 2月 10日 12:05 这就是sliding tile jigsaw puzzle
最简单的是3x3
常见的还有4x4
我过去没玩过，但我家小孩在1年级上下那几年里玩过。在美国应该很受欢迎。
Re: 3x3的棋盘
meiyoumajia 写了： 2023年 2月 10日 11:29 对原题，也就是3x3，我时有具体的办法把8到3一个个放到最终的位置。如果要考虑有效办法/“算法”，对每个的做法有时会有些不同。
如果也要考虑更大的n，比如5x5，但不考虑算法/解决问题方法的有效程度，而只考虑数学问题，那就可以按下面的做法一步步退化/约化。
只考虑需要被处理的情况
对3x3：
如果要处理的数a不在最终安置位（8，7和6等被依次紧密放在最下方，从最右下角开始），
0。如果a在角上，把a-1或者以下一个放在中央，转整个外圈1次（7个操作，造成a离开了角），把中央数字填到空位
把a放在中央
把a放在a+1前（有时，也要做上面那种对外圈的针对“0。”情况的外圈反转/转，更多的转和部分转）
这样就能约化1步
此法可用于5x5等奇数边长的情况。从外圈做起，“中央”是3x3，复杂不少，要把a先放在中央3x3的外圈。在5x5的外圈完全定好最终位后，就是3x3定位的问题了。最后看它的开始两个数是否顺序/逆序。
这个解释充分性略有问题
因为"能够把一个数字移到最终位置"不是可解的充分条件
Re: 3x3的棋盘
充要性都反映在了最后那仅有的2种可能情况里。
无论3x3（还是奇数nx奇数n）最开始的分布状态是什么，我所有做的建设性方法（constructive method）最后只可能是那二者之一。（它们的区别是根本的。任何个可允许操作都没法让最后那个213所在分布变成12。。。8分布---两种种的另外一种。）
Re: 3x3的棋盘
这是对8到3的建设性处理方法，都是可行的。（而且每一步都是可逆性的。）那些是方法，而不是什么任何条件。没对2和1做，我的约化到3就止住了。
做完3后，或是21345678，或是12345678，而这两个由于奇偶性不同，互相排斥，相互不能转换成对方。
其实是：
逐次对8到3中的每一个，没空位地逐次排位到3x3的最后还没有占据的最终位置。（比如做完8，7和6，那5就该排在第二行的最后。）每步都没有任何问题。
Re: 3x3的棋盘
3的情况特殊，应该分别处理。昨天我做过，好像没有什么问题。你可验证。
8 和7很容易到位。做6时，会有等效于最后一行是a78的情况（a非6），把6转到7的正上方（也就是正中央），876带着a以外的逆时针走1步，中央放上剩下4位中的一个，876带上a逆时针沿着外圈走到最后一行是678。然后很快能定5。
对4最不容易定位的是（ab4c+空位）开始的分布
把b4移动1步，5b4移动1步，ac移动1步，4b5移1步，a一步，b一步。4就到位了。
而3在中间的情况所用方法，我在最近的一帖里表述过了
另外的情况中，只考虑最多步骤的情况；3在角上，（ab3+空），
ab3移动1次，543移动1次，ba移动一次，345移动1次，ba移动一次
只是我最后得出的是
（空位）ab
345
678
而不是
ab3
456
78（空位）
因此有一个大错误：完全做反了。
但是
把上面的所有步骤都反过来应该就可以了。
上下，左右，顺时对逆时针。。。
最后形式
123
456
ab（空位）
8 和7很容易到位。做6时，会有等效于最后一行是a78的情况（a非6），把6转到7的正上方（也就是正中央），876带着a以外的逆时针走1步，中央放上剩下4位中的一个，876带上a逆时针沿着外圈走到最后一行是678。然后很快能定5。
对4最不容易定位的是（ab4c+空位）开始的分布
把b4移动1步，5b4移动1步，ac移动1步，4b5移1步，a一步，b一步。4就到位了。
而3在中间的情况所用方法，我在最近的一帖里表述过了
另外的情况中，只考虑最多步骤的情况；3在角上，（ab3+空），
ab3移动1次，543移动1次，ba移动一次，345移动1次，ba移动一次
只是我最后得出的是
（空位）ab
345
678
而不是
ab3
456
78（空位）
因此有一个大错误：完全做反了。
但是
把上面的所有步骤都反过来应该就可以了。
上下，左右，顺时对逆时针。。。
最后形式
123
456
ab（空位）
上次由 meiyoumajia 在 2023年 2月 10日 16:36 修改。