问题描述

在 3 * 3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的 问题是，给出一种初始布局 [ 初始状态 ] 和目标布局 [ 目标状态 ] ，找到一种移动的方法，实现从初始布局到目标布局的转变。

输入格式

输入由两行组成，每行8个数，分别表示初始状态和目标状态：

输出格式

有若干行，第一行表示最小步数 ，接下来的每行输出一步的状态,如果在6步内无法达到目标状态，输出“No solution!”。

样例

283164705
123804765

5 
283164705
283104765
203184765
023184765
123084765
123804765