八数码难题也称九宫问题,它是在3×3的方格棋盘上,分别放置了表有数字1、2、3、4、5、6、7、8的八张牌,初始状态S0,目标状态Sg,要求程序能输入任意的初始状态和目标状态,要求通过空格来移动八张牌使得棋盘由初始状态到达目标状态。移动规则为:每次只能将与空格(上下左右)相邻的一个数字平移到空格中。