Backtracking
回溯法
解的時候就如圖:
類似暴力解
但又不是全部的組合都試?!
所以效率算不錯 吧 嗎
中心思想就是
先填好這個，檢查之後有沒有衝突，沒有就繼續填下一個，有就代表填錯重新填
也就是遞迴的概念OAO
第一個參考資料說明:
回溯法 ( 探索与回溯法 ) 是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
簡單範例說明 : (好爛....
第一格填 1 發現沒有衝突，填第二格發現不管填 1~9 都會衝突
那就代表可能上一格填錯
所以返回第一格，填 3 發現沒衝突，第二格也有數字填
這樣就可以繼續下去了
至於怎麼檢查之後有沒有衝突，
方法就是呼叫檢查函式
檢查函式接收到一個 index 後
就去檢查這個 index 所在的 row 跟 col 跟 cell 有沒有衝突
所謂衝突
就是找到一樣的數字
有衝突，回傳false
沒衝突，回傳true
程式碼就不說明了
範例程式可在回溯法求解数独（C++实现）得到
突然覺得沒什麼好講的QAQ
實際實作就連到我的Github囉 ( 自己的作業自己寫OuO )
README有說明一下要怎麼使用
不是直接編譯 Sudoku.cpp就可以喔!!!!
怎麼編譯就請看Makefile裡的東西吧
超不負責記錄●完
參考資料:
回溯法求解数独（C++实现）
演算法筆記- Backtracking
沒有留言:
張貼留言