八数码问题又称重排九宫问题,在一个33的棋盘上,随机放置1到8的数字棋子,剩下一个空位,如图所示。数字可以移动到空位(编程时,空位可用0代替,且可以理解为是空位的上、下、左、右移动),经过若干次移动后,棋局到达指定目标状态。  说明:重排九宫问题,对任意给定初始状态,可达下图所示两个目标之一,不可互换。