Lab2: SoDuKu Solver 2

"

資工三甲 493511151 黃鼎峰

 

 

Sudoku演算法介紹:

     這次我所使用的演算法基本上還是沿用我上次的演算法去做改進 , 先稍微說明我上次所使用的演算法 , 基本上我是利用遞回來去實作backtracking,演算法一開始會由左到右由上到下一行一行的去search需要填的位置,當碰到第一個空格後 ,會檢查這個空格可以填入哪些數字 ,之後把可以填入的數字填入再call我solve的function ,當檢查到無法填入的格子會backtracking回去,直到找出答案

    再來要說我Lab2的改進方法 , 基本上我程式的基底並沒有改 , 我只是多家一些步驟 ,而那些步驟大至上是檢查出要填入的格子中哪一個有最少候選值(也就是可以填入的數字各數),找到後先對那個格子做處裡 ,我會這樣作的理由為 ,先從最少候選值的格子丟數字 , 理論上可以有效的減少程式需要展開的tree大小 ,可是因為每次都要檢查所有的格子 ,所以也可能會有變慢的情況 .

Lab2和Lab1的實際比較:

    在我實作Lab2的程式後 , 和Lab1的比較結果令我有些訝異 , Lab2的運算時間有的比Lab1慢有的比較快 , 基本上在Lab1運算時間需要比較短的Sudoku大部分都變的比較慢 , 只有少數變快 , 可是也沒慢多少 大概 1~20 ms ,可是Lab1需要較多時間運算的Sudoku速度都有大幅度的成長 ,其中最明顯的為2-2 , Lab1需要約200ms而Lab2花的時間比Lab1快10倍 .

結論:

    我想其中運算時間的差異主要是差在找出最少候選值的格子上吧 , 當Cost大於減少tree大小的Cost後 , 其運算時間就會變慢 , 然而面對需要展開大量tree的Sudoku ,Lab2的演算法就有了顯著的成長 . 

"