摘要:[Java] Android遊戲－倒水解謎的解題程式
倒水解謎是一款Android遊戲，玩法是有3個不同容量的杯子還有一個可以把杯子裝滿水的水龍頭，互相裝來倒去之後，要讓指定容量的杯子裡面剛好有特定量的水。
這個遊戲有4種難度，分別是菜鳥、專家、極限、壓力。本文的解題程式只能解決菜鳥、專家與壓力難度的題目，因為我在寫解題程式的時候沒有發現極限難度的題目有兩組要求，所以只針對一組要求來解題。
我的解題概念很直觀(也很笨)，有3個杯子，每個杯子都有4種動作:把水倒在另A杯、把水倒在另B杯、裝滿水、倒光，使用暴力法去遞迴求解。
簡單介紹完之後，就來看看實際的例子，以下是菜鳥難度第1關的題目
程式的執行結果
專家難度第1關的題目
程式的執行結果
解題程式可以找出最佳步數下所有解的步驟，並一一列出來，不過有時候並不需要看各種解的詳細步驟，因為只需要一組最佳步數的解就可以破關拿3星，所以在這部分可以修改參數來調整輸出的內容(於Main.java第40行)。
不過最關鍵的執行效率頗不理想，以菜鳥難度第45關來說，最佳步數為8，花費時間竟高達25秒，看來還有很多改進的地方。
由於程式碼加上滿滿的註解就超過200行，所以就不在本文中附上任何程式碼。
*最新版本* 專案下載(NetBeans): 倒水解謎之解題程式.zip
另外也附上先前的版本
2013-04-14: 倒水解謎之解題程式.zip 因點部落改版，此載點已經失效
題外話: 我在學校這學期剛好是上Java課，所以解題程式就使用Java來實作，順便當作練習，變數命名跟註解的寫法還不是很熟悉，如果有不好的地方還請多多指教。
2013-04-15更新:
發現先前的版本效率低落的原因在於遞迴時的解題步驟使用字串String型態去傳送，如果完全不記錄解題步驟，只單純計算有幾組解跟最佳步數的話，是可以在1秒內完成計算，不過寫這個解題程式就是為了要看步驟，所以為了提高程式的執行效率，必須針對解題步驟的記錄來調整。
原本是在每次遞迴的時候都建立新的字串，所以效率很差，於是我先改用List<String>來取代String，雖然速度有比較快，但還不是很滿意，之後我改用List<Integer>並將步驟的所有數據格式化成我自訂的「整數」格式，最後再一次輸出成可閱讀的文字解題步驟。此舉效果顯著，所以就來做個筆記。
前一個版本在解菜鳥難度第45關耗時高達25秒，但是在這個版本已經可以秒殺了。
就算把每組可行解的都找出來，也是秒殺。
另外此版本還修正了一個小BUG－是否要記錄所有可行解，如果false的話應該只需要找出一組解，當true才要找出所有解，所以以上面2張圖來看，同樣一組測資，但是上面的圖(isShowAllSolution = false)只找到1組解，下面的圖(isShowAllSolution = true)卻找到4組解。前一個版本是都會找到4組解，但是就差在印出1組還是全部。
文章內容僅提供技術分享，如有錯誤還請不吝指教。
