數獨題目的難易程度可以用題目中的提示數多寡來區隔，提示數越少者難度越高，然而過少的提示數會使得盤面因為具有多個解或甚至無解而成為無效的數獨盤面，所以剛好產生唯一解且提供最少個提示數的數獨盤面就稱之為「最少提示數之數獨盤面」。而現今已知的最少提示數之數獨盤面其提示數為17，是否存在16個提示數的數獨盤面，仍是個未解的難題。
本篇論文有兩個主要方向，其一是藉由已知的17個提示數盤面透過「基因重整繁衍」之演算法，產生一代代不同的17個提示數之候選數獨盤面，之後透過改寫「Solver」程式而成的「Quick Solver」做唯一解的篩檢，以及重複性的篩檢，組合成「17個提示數之數獨盤面產生器」。其二則是藉由「17個提示數之數獨盤面產生器」所產生出來的大量17個提示數之數獨盤面，將每個新生的17個提示數之數獨盤面刪減一個提示數形成17倍的16個提示數之數獨盤面，再將這些16個提示數之數獨盤面做唯一解的篩檢，企圖利用此一方式能找到16個提示數之數獨盤面。此方法比純用亂數來產生16個提示數之數獨盤面的成功機率會高很多。
經過本研究的系統實作，以約一個月的時間繁衍出八代新生子代，總計獲得超過20萬筆的17個提示數之有效數獨盤面。又利用這些新生成的17個提示數之數獨盤面產生超過340萬筆的16個提示數之候選盤面，但很可惜的，尚未找到16個提示數之數獨盤面。希望未來能有找到的機會。

Sudoku can be categorized into several levels depending on the number of hints given. It is known that too few hints may lead to inconsistent solutions: either many or no solutions at all. To date the best-known minimum number of hints to consistently solve a Sudoku is 17. It is still an open question whether there exists a Sudoku with 16 hints which can also give a consistent solution.
The strategies of this thesis are as follows. Firstly, we use 17-hints Sudokus as a basis to generate new 17-hints sodukus to widen our search space. We rewrite the “Solver” program to become “Quick Solver” which can filter new 17-hints Sudokus and insure that those new 17-hints Sudokus are all have one solution only. We use the “genes restructuring” algorithm to create new Sudokus which are then filtered to avoid redundant and inconsistent candidates.
Secondly, we use these 17-hints Sudokus to generate all 16-hints Sudokus by removing one of the hints. The likelihood that this approach will lead to consistent 16-hits Sudokus is much higher compared to random-generated 16-hints Sudokus. All 16-hints Sudokus are then tested for consistency.
After implement the system proposed in this thesis, we found out that more than 200,000 valid 17-hints Sudokus had been produced using about one month of computation time. It’s quick and efficient. Through those 200,000 17-hints Sudokus we can also generate more than 3 million 16-hints candidate Sudokus. Unfortunately, up to now, we still can not find out any valid 16-hints Sudoku. We hope that we can make it in the near future.

[1]B. Felgenhauer and F. Jarvis, “Enumerating possible Sudoku grids,” In http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf, 2005.
[2] B. Felgenhauer and J.Frazer, “Mathematics of Sudoku I,” In http://www.afjarvis.staff.shef.ac.uk/sudoku, 2005.
[3] B. Felgenhauer and J. Frazer, “Mathematics of Sudoku II,” In http://www.afjarvis.staff.shef.ac.uk/sudoku, 2006.
[4] S. Gupta, “Some results on Sudoku,” In http://theory.tifr.res.in/~gupta/sudoku/theorems.pdf, 2006.
[5] T. Koch, “Rapid mathematical programming or how to solve Sudoku puzzles in a few seconds,” In Konrad-Zuse-Zentrum fur Informationstechnik Berlin, pp.5-51, 2005.
[6] I. Lynce and J. Ouaknine, “Sudoku as a SAT problem,” In 9th International Symposium on Artificial Intelligence and Mathematics, pp.3-5, 2006.
[7] A. Moraglio, J. Togelius, and S. Lucas, “Product geometric crossover for the Sudoku puzzle,” In Proceedings of IEEE CEC 2006, pp.1-6, 2006.
[8] G. McGuire, “Sudoku checker and the minimum number of clues problem,” In http://www.math.ie/checker.html.
[9] E. Russel and F. Jarvis, “There are 5472730538 essentially different
Sudoku grids,” In http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html.
[10] G. Royle, “Minimum Sudoku,” In http://www.csse.uwa.edu.au/~gordon/sudokumin.php.
[11] H. Simonis, “Sudoku as a constraint problem,” In CP Workshop on Modeling and Reformulating Constraint Satisfaction Problems, pp.13-27, 2005.
[12] T. Yato and T. Seta, “Complexity and completeness of finding another
solution and its application to puzzles,” In Proceedings of the National Meeting of the Information Processing Society of Japan(IPSJ), pp.2-7, 2002.
[13] “Latin square wikipedia entry,” In http://en.wikipedia.org/wiki/Latin_square.
[14] “Mathematics of Sudoku of wikipedia entry,” In http://en.wikipedia.org/wiki/Mathematics_of_Sudoku..
[15] “Sudoku -- one for the puzzles by pappocom,” In http://www.sudoku.com.
[16] “Sudoku wikipedia entry,” In http://en.wikipedia.org/wiki/Sudoku.