雙洞推盤（two-hole puzzle）遊戲據說起源於台師大資工系，在 $\text{2021}$ 年起風行於台灣。本題考量解題時間，將盤面固定為 $4\times 4$，且其中最上兩排的 $8$ 個單格由左而右、由上而下，依序填入 $1$ 到 $8$ 的 $8$ 個數字，接下來剩下的單格隨機填入 $9$ 到 $14$ 的數字，而留下兩個空的單格(稱為雙洞），形成起始狀態，而空的單格可以由相鄰的上、下、左或右方有數字的單格移入其數字。雙洞推盤問題研究如何找出數字移入空格的最少步數的方式，藉以達成最後由上而下、由左而右，依序由 $1$ 到 $14$ 排序的目標狀態。舉下圖為例，由某個起始盤面至終點盤面，一個走最少步數的範例如下：

　　請你寫一程式來求出最佳的走法，也就是走最少步數的走法。注意：我們給定的起始盤面一定會有解。