如何以编程方式解决15个(移动数字)难题？

Question

你们所有人都可能已经看过移动的数字/图片拼图.你在4x4网格中有1到15的数字,并试图从随机起始位置获取它们的那个

1   2  3  4
5   6  7  8
9  10 11 12
13 14 15 

我的女朋友或我的一些非程序员朋友可以通过一些愚蠢的魔法来解决这个问题,他们无法向我解释.我无法解决这个难题.

我发现最有希望的方法是解决第一行,然后我会得到

1   2  3  4
X   X  X  X
X   X  X  X
X   X  X 

然后第一列没有触及解决的细胞

1   2  3  4
5   X  X  X
9   X  X  X
13  X  X 

然后第二排到

1   2  3  4
5   6  7  8
9   X  X  X
13  X  X 

然后是第二栏

1   2  3  4
5   6  7  8
9   10  X  X
13  14  X 

问题是,剩余的X(随机)磁贴有时处于无法解决的位置,这就是我的解决方案失败的地方.但我觉得好像我走在了正确的道路上.

我的程序通过尝试将数字X到达指定位置来解决指定的行/列,如果可能的话,不会弄乱正确的单元格.但它无法在2x2网格上完成最后3个图块.我错过了什么？

Answer 1

确保您的拼图首先是可解决的. 不是全部.

否则你的策略看起来很合理

Answer 2

你肯定是在正确的轨道上,而不是通过行/列迭代地解决到剩下的2x2,解决直到你有一个最小的3x3然后解决那个网格.3x3是正确重新排序网格所需的最小尺寸(而2x2并不能提供您可能需要的完全灵活性,如您已经讨论过的那样).这种方法也是可扩展的 - 你可以解决5x5,10x10等问题.