題解

總共 9! 種狀態，求最佳解，直觀想到使用 BFS。

但直接 BFS 會 TLE，因此觀察發現結尾盤面固定。
則改從結尾盤面出發，將操作逆向，找出所有可能拓展的盤面。
如此對於所有輸入，皆可直接回答是否無解，若有解則可回溯出一組走法。

雖然未曾嘗試，雙向 BFS 也許也有機會 AC。