why-is-the-15-puzzle-unsolvable

15数码游戏为什么无法解决

“15数码游戏”，也称为“15数字难题”，并非无法解决，而是某些初始状态无法达到目标状态。

游戏描述

“15数码游戏”是一款滑块游戏，游戏棋盘是一个4×4的网格，包含15个标记为1到15的滑块和一个空格。玩家的目标是将滑块按照从左到右、从上到下的顺序移动，最终使滑块排列为1到15的有序序列，并将空格置于右下角。

无法解决的情况

只有当初始状态的逆序对数量为奇数时，才能确定该状态无法通过合法移动达到目标状态。逆序对是指在序列中，两个数字的前后位置与其大小顺序相反。例如，在序列2、4、3、1中，逆序对为(2, 1)、(4, 3)、(4, 1)、(3, 1)，总共有4个逆序对。

证明

棋盘上滑块的移动可以视为这些滑块排列的变换。每次移动一个滑块时，实际上是将空格与相邻的滑块交换。而这种交换操作改变了排列的逆序对数的奇偶性。目标状态的逆序对数为0，即偶数。如果初始状态的逆序对数为奇数，无论移动多少次，其逆序对数都无法改变为偶数，因此无法达到目标状态。

如果你也喜欢玩Puzzles ball，它是完全免费、有趣且易于上手的。