N-拼图游戏的可解性

所谓的N-拼图 (N-puzzle) 是一种流传很久的智力游戏,是谁发明已无法考证。1865年Embossing公司发售了这款游戏的一个版本,使得其风靡一时。常见版本的有 8 块和 15 块的两种,非常类似游戏“华容道”。以 15 块的拼图为例,玩家需要通过移动一个方形容器中的各个小方块,将一副打乱的拼图恢复成初始形态(如下图)。
15-puzzle Continue Reading…