11513 - 9 Puzzle

Alex有一個類似拼圖的小玩具，該玩具上有數字1~9分別對應到 3 x 3 的方格中，該玩具允許兩種移動方式：

• 在任一列的三個數字中，水平地向右循環移動一格。
• 在任一行的三個數字中，垂直地向上循環移動一格。

有一天該玩具上的所有數字被不小心撞壞掉落，雖然事後已經修復但其上的數字卻被隨意放置，本題請你找出最少的移動步驟使之可以回復到下圖的狀態：

1	2	3
4	5	6
7	8	9

當然並非一定可以回復到上圖的狀態。

Input

輸入有多組測試資料，每組資料三列，每列三個整數，並以一個空白字元隔開。測試資料的最後以一個0表示資料結束。

Output

請對每組測試資料輸出最少移動的次數，且輸出移動的步驟為何，每個步驟以兩個字元表示，第一個字元以H表示水平移動，以V表示垂直移動，第二個字元分別以1, 2, 3表示移動哪一列或哪一行。若無解請輸出"Not solvable"。

Sample Input

2 3 1
4 5 6
7 8 9
7 3 9
2 5 1
4 8 6
1 2 3
4 5 6
7 9 8
0

Sample Output

1 H1
3 V1V3H1
Not solvable

---

原文出處