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