宅學習 - Social Learning Space 社交學習空間@FJU CSIE

"

註：這篇文章原po於無名小站blog
引用自～「Lab3: SuDoKu Solver 3」～

資工四甲 492511635 林泰昇

　　這次的作業並沒有實做新的候選數消去法，由於從Lab1以來都是使用backtracking實做，因此這次Lab的重點還是和Lab2相同──最佳化(optimization)。

　　承襲Lab2，這次進行的optimization的重點在於：

1. 改寫class，改變class基本結構，減少使用object data type的地方，儘量採用primitive data type。
2. 改寫backtracking method，增加backtracking的效率。
3. 改變呼叫method的順序，減少多餘的檢查次數。
4. 由於Lab2雖然大幅改進Lab1的效率，但backtracking的次數卻大幅增加。根據實驗結果，backtracking次數越多，所花費的運算時間就會越高。Lab3修正這點降低backtracking的次數。

經過三次Lab的改進後，總結心得如下：
　　這三次的Lab讓我相當深入的瞭解sudoku遊戲的運作與解題技巧，原本我並沒有接觸過這個遊戲，在完成三次Lab後，像x-wing這種較進階的解題技巧都能清楚其運作原理，這是意想不到的收穫(或痛苦)。

　　其次就是熟悉backtracking的背後原理與實際運用。對於backtracking的理論與應用都有了更進一步的瞭解，也讓我對演算法增加了不少興趣，這是做完Lab後最大的收穫。

改進事項與未來目標

1. 三次Lab的backtracking都沒有使用recursive實做，也許其中一兩次應該改成recursive。這樣的話相信可以更增進對backtracking的瞭解。
2. 程式效率還是不盡理想。也許整個程式的結構都需要分別改進才能進一步得到更好的效率(Greedy？)
3. 程式結構不夠清楚。雖然和演算法主題無關，不過就物件導向程式來說，程式必須能夠適應變化才是最好的，我的程式顯然還是離這個目標有很大的距離。
4. 可增加GUI介面，這樣可以使程式提供更佳的人機介面，最好能再提供操作介面讓使用者匯入題目，增加程式的友善性。

執行結果與比較
　　以下是各題經程式執行後的結果，和三次Lab的比較表格：

註1：三次Lab均在同機器下執行。
註2：計算時間為呼叫method System.nanoTime()，這邊所列時間為運算和製作log file合計之時間，不含顯示所花時間，三次Lab計時機制相同。

圖1  Lab2和Lab3解題時間的比較(由於4-7耗費太多時間，顯示的話難以比較出其他題的改變程度，因此不列在表中)

圖2  三個Lab解題時間比較

[sdk1-1.txt]
題目：
7 8 1 6 - 2 9 - 5
9 - 2 7 1 - - - -
- - 6 8 - - - 1 2
2 - - 3 - - 8 5 1
- 7 3 5 - - - - 4
- - 8 - - 9 3 6 -
1 9 - - - 7 - 8 -
8 6 7 - - 3 4 - 9
- - 5 - - - 1 - -

花費 7.896814 毫秒

最後結果：
7 8 1 6 3 2 9 4 5
9 5 2 7 1 4 6 3 8
4 3 6 8 9 5 7 1 2
2 4 9 3 7 6 8 5 1
6 7 3 5 8 1 2 9 4
5 1 8 4 2 9 3 6 7
1 9 4 2 6 7 5 8 3
8 6 7 1 5 3 4 2 9
3 2 5 9 4 8 1 7 6
================

[sdk1-2.txt]
題目：
- - 2 5 4 7 3 6 -
4 6 5 - - 3 - - 7
7 3 - - - 6 8 - 5
- - 6 8 1 5 4 7 9
- - - 3 6 4 5 - -
- - 4 - - - - - -
- 5 7 - - 8 - - -
- 4 - 6 - 1 - 9 -
- 9 8 7 - - - 5 -

花費 4.136559 毫秒

最後結果：
9 8 2 5 4 7 3 6 1
4 6 5 1 8 3 9 2 7
7 3 1 9 2 6 8 4 5
3 2 6 8 1 5 4 7 9
8 7 9 3 6 4 5 1 2
5 1 4 2 7 9 6 8 3
1 5 7 4 9 8 2 3 6
2 4 3 6 5 1 7 9 8
6 9 8 7 3 2 1 5 4
================

[sdk1-3.txt]
題目：
4 - - 8 9 3 2 - -
- 2 - 1 - 4 - 3 -
- 9 - - 2 6 4 - 5
- - 8 - - 9 - 5 4
- - - 3 - 1 7 2 8
3 7 - - - 5 1 - -
- 3 9 - - - - 1 7
- 8 6 - - - - - -
- - 1 - - - 9 - 2

花費 7.772217 毫秒

最後結果：
4 6 5 8 9 3 2 7 1
8 2 7 1 5 4 6 3 9
1 9 3 7 2 6 4 8 5
6 1 8 2 7 9 3 5 4
9 5 4 3 6 1 7 2 8
3 7 2 4 8 5 1 9 6
5 3 9 6 4 2 8 1 7
2 8 6 9 1 7 5 4 3
7 4 1 5 3 8 9 6 2
================

[sdk1-4.txt]
題目：
- - 7 - 6 - - 3 -
9 - - - - - 1 4 -
- 6 4 - - 5 - - -
1 - - - - 8 - - 5
- - - 5 7 - 9 1 -
5 3 9 - 4 - - 6 -
6 - - - 5 1 - 7 2
2 - - - 3 7 6 - 1
- - - 6 - - - - -

花費 2.252242 毫秒

最後結果：
8 1 7 2 6 4 5 3 9
9 5 2 7 8 3 1 4 6
3 6 4 9 1 5 2 8 7
1 7 6 3 9 8 4 2 5
4 2 8 5 7 6 9 1 3
5 3 9 1 4 2 7 6 8
6 9 3 4 5 1 8 7 2
2 4 5 8 3 7 6 9 1
7 8 1 6 2 9 3 5 4
================

[sdk1-5.txt]
題目：
- 7 - - - 2 3 - 4
- - 9 - 5 3 - - -
- - 4 - - - - - -
- - - - - - - - 8
- - - 6 - 8 1 9 -
- - 7 2 - - - 5 -
- 8 - - 1 - 4 - -
- 6 - - - - 7 - -
- 3 2 - - - - - -

花費 0.926095 毫秒

最後結果：
5 7 8 9 6 2 3 1 4
6 1 9 4 5 3 8 7 2
3 2 4 1 8 7 5 6 9
1 9 6 7 3 5 2 4 8
2 5 3 6 4 8 1 9 7
8 4 7 2 9 1 6 5 3
7 8 5 3 1 9 4 2 6
9 6 1 8 2 4 7 3 5
4 3 2 5 7 6 9 8 1
================

[sdk2-1.txt]
題目：
- 8 - - - - - - -
- 4 7 8 - 9 - - 1
- - 1 4 5 - - 2 -
8 1 6 7 - - 5 - -
9 - - - - 1 - - -
- - - 5 6 - - - -
- - - - - 8 - 5 3
- - - - - - - 8 -
- - - 3 1 - - 4 6

花費 2.110324 毫秒

最後結果：
6 8 2 1 3 7 4 9 5
5 4 7 8 2 9 3 6 1
3 9 1 4 5 6 7 2 8
8 1 6 7 9 4 5 3 2
9 3 5 2 8 1 6 7 4
2 7 4 5 6 3 8 1 9
4 2 9 6 7 8 1 5 3
1 6 3 9 4 5 2 8 7
7 5 8 3 1 2 9 4 6
================

[sdk2-2.txt]
題目：
- - - 7 - - - - 2
- - - - 3 6 - - -
- - 5 - - - - 3 -
- - 8 - - 2 5 4 -
7 - - 4 - 9 - - -
- - - - - - - - 6
- 4 3 - 7 - - 2 -
- - - - - - 9 - -
- 7 - 1 5 - - - -

花費 1.885435 毫秒

最後結果：
3 1 4 7 9 5 6 8 2
9 2 7 8 3 6 4 5 1
8 6 5 2 4 1 7 3 9
1 9 8 3 6 2 5 4 7
7 5 6 4 8 9 2 1 3
4 3 2 5 1 7 8 9 6
6 4 3 9 7 8 1 2 5
5 8 1 6 2 3 9 7 4
2 7 9 1 5 4 3 6 8
================

[sdk3-1.txt]
題目：
- - 2 - - 1 4 - -
7 - - 3 8 - - 2 6
- - 6 - - - - - 5
- - 9 - - - - - 8
1 - - - - 3 9 - -
8 - - - - 2 - - -
- - - 2 - - - - -
5 - - - - - - - 4
- - 7 - - 9 6 - -

花費 1.129753 毫秒

最後結果：
3 8 2 6 5 1 4 7 9
7 9 5 3 8 4 1 2 6
4 1 6 9 2 7 8 3 5
6 2 9 1 7 5 3 4 8
1 7 4 8 6 3 9 5 2
8 5 3 4 9 2 7 6 1
9 3 8 2 4 6 5 1 7
5 6 1 7 3 8 2 9 4
2 4 7 5 1 9 6 8 3
================

[sdk3-2.txt]
題目：
7 - 8 1 4 - - - -
- 6 5 - - - 4 2 -
3 4 - 9 - - - - -
6 - - - - - - 7 5
- - - - 9 - - 4 -
- - 3 - - - - 6 -
1 9 - 8 - 6 - - 7
- - - 4 - - - - -
5 - - - 3 - - - 4

嘗試代入次數=2
花費 7.266287 毫秒

最後結果：
7 2 8 1 4 5 3 9 6
9 6 5 7 8 3 4 2 1
3 4 1 9 6 2 7 5 8
6 1 9 3 2 4 8 7 5
8 5 2 6 9 7 1 4 3
4 7 3 5 1 8 9 6 2
1 9 4 8 5 6 2 3 7
2 3 6 4 7 1 5 8 9
5 8 7 2 3 9 6 1 4
================

[sdk4-1.txt]
題目：
4 - - - 2 3 - - -
- - - 5 9 6 7 - -
- 9 - 7 - - - - -
8 - - - - - - - -
- - 5 - - - 1 6 -
- - - - - - - 9 4
- 8 - - - - - - -
9 - - - - 2 - - 3
6 - 3 8 5 4 - 1 2

嘗試代入次數=3
花費 12.192611 毫秒

最後結果：
4 5 7 1 2 3 6 8 9
3 2 8 5 9 6 7 4 1
1 9 6 7 4 8 2 3 5
8 3 9 4 6 1 5 2 7
2 4 5 9 3 7 1 6 8
7 6 1 2 8 5 3 9 4
5 8 2 3 1 9 4 7 6
9 1 4 6 7 2 8 5 3
6 7 3 8 5 4 9 1 2
================

[sdk4-2.txt]
題目：
- 2 - - 3 - - - 4
- 1 9 - 2 - - 8 -
7 - 8 - - - - - -
2 7 6 - - 4 3 - -
8 - - - - - - - 6
- - - - 8 - - - -
- - - - 6 - - 9 5
- - - 5 - 9 - - -
- - 3 7 - - - - -

花費 0.988953 毫秒

最後結果：
6 2 5 8 3 7 9 1 4
3 1 9 4 2 6 5 8 7
7 4 8 9 5 1 6 3 2
2 7 6 1 9 4 3 5 8
8 9 4 3 7 5 1 2 6
5 3 1 6 8 2 7 4 9
1 8 7 2 6 3 4 9 5
4 6 2 5 1 9 8 7 3
9 5 3 7 4 8 2 6 1
================

[sdk4-3.txt]
題目：
- 9 4 - 3 6 2 - -
- 7 - - - - - - 5
- 3 - 4 - - - - -
- - - 8 - 1 5 - -
- 2 - - 4 - - - -
7 - - - - - - - 6
8 - - - 5 7 9 - -
- - - - - - 3 - -
- - - - - 2 - - 7

嘗試代入次數=5
花費 8.280661 毫秒

最後結果：
5 9 4 7 3 6 2 8 1
6 7 1 2 9 8 4 3 5
2 3 8 4 1 5 7 6 9
3 4 6 8 7 1 5 9 2
1 2 5 6 4 9 8 7 3
7 8 9 5 2 3 1 4 6
8 6 2 3 5 7 9 1 4
9 5 7 1 6 4 3 2 8
4 1 3 9 8 2 6 5 7
================

[sdk4-4.txt]
題目：
- - 5 - - - - - -
- - 4 8 6 - 9 - -
- - - 3 - 7 8 - -
- - - - 4 2 - - 7
- - 2 - - - - - -
1 - - - - 8 6 - -
- 8 - - 9 - 7 - -
- - - - 1 5 - - 6
6 - - - - - - - 4

花費 1.305193 毫秒

最後結果：
8 7 5 9 2 4 1 6 3
2 3 4 8 6 1 9 7 5
9 1 6 3 5 7 8 4 2
3 9 8 6 4 2 5 1 7
5 6 2 1 7 9 4 3 8
1 4 7 5 3 8 6 2 9
4 8 3 2 9 6 7 5 1
7 2 9 4 1 5 3 8 6
6 5 1 7 8 3 2 9 4
================

[sdk4-5.txt]
題目：
- 2 - - - 1 - - 4
5 - - 7 6 - - - -
- - 7 - - - - - 8
1 - 6 - - - - - -
- 8 - - - 5 - 3 -
- 7 - - - - 4 9 -
- - 8 - 3 - 5 - -
- - - 8 - - 2 - -
6 - - - 5 - 3 - -

嘗試代入次數=3
花費 5.701562 毫秒

最後結果：
8 2 3 5 9 1 7 6 4
5 1 4 7 6 8 9 2 3
9 6 7 3 2 4 1 5 8
1 5 6 9 4 3 8 7 2
4 8 9 2 7 5 6 3 1
3 7 2 1 8 6 4 9 5
2 4 8 6 3 7 5 1 9
7 3 5 8 1 9 2 4 6
6 9 1 4 5 2 3 8 7
================

[sdk4-6.txt]
題目：
- 5 - - 7 - - - -
1 7 8 - - - - - 9
- 9 6 - - - - - 3
3 - - - - 1 - - 8
- - 9 4 3 - 7 - -
- - - 2 - - 6 - -
- 3 7 - 2 - - 6 -
8 - - 3 5 - 4 - -
- - - - - - - - -

嘗試代入次數=3
花費 3.629511 毫秒

最後結果：
2 5 3 1 7 9 8 4 6
1 7 8 6 4 3 2 5 9
4 9 6 5 8 2 1 7 3
3 4 5 7 6 1 9 2 8
6 2 9 4 3 8 7 1 5
7 8 1 2 9 5 6 3 4
9 3 7 8 2 4 5 6 1
8 1 2 3 5 6 4 9 7
5 6 4 9 1 7 3 8 2
================

[sdk4-7.txt]
題目：
- 1 9 - - - - - -
- - 8 - - 3 - 5 -
- 7 - 6 - - - 8 -
- - 1 - - 6 8 - 9
8 - - - 4 - - - 7
9 4 - - - - - 1 -
- - - - - 2 - - -
- - - - 8 - 5 6 1
- - 3 7 - - - 9 -

嘗試代入次數=20
花費 24.976358 毫秒

最後結果：
5 1 9 4 2 8 7 3 6
6 2 8 9 7 3 1 5 4
3 7 4 6 1 5 9 8 2
7 3 1 2 5 6 8 4 9
8 6 5 1 4 9 3 2 7
9 4 2 8 3 7 6 1 5
1 8 6 5 9 2 4 7 3
2 9 7 3 8 4 5 6 1
4 5 3 7 6 1 2 9 8
================

三次Lab的比較表(時間取小數點第二位四捨五入)

"