练习编程的题目

aubell

发现这样一个好题目，很适合练习编程：
大家有兴趣试试吗？手动求解很容易，但求到最短步数不一定很容易。
要求用计算机求最少步数。
题目描述：
棋盘是7个空格
棋子有6个，编号1-6，排一排，棋盘最右边留一个空格
走法：1.挪动一个棋子 2.跳动一个棋子，进入空格中
目标：把123456变成654321，仍放在最左边的6个格子里。

说明：由于只有一个空格，所以可以直接用数字表示走法。
例如一个解法是：6 4 2 1 3 5 6 4 2 1 3 5 6 4 2 1 3 5 6 4 2
共21着。

您能找到其它解法吗？换成9个格子，8个棋子呢？更多呢？