數獨之最少提示數研究

Abstract

數獨遊戲的風行已經有幾年了，這段時間中陸續有各式解題法被開發出來，其中以候選數演算法最廣為大家所使用。近幾年盤面產生器成了新的研究風潮，其中林順喜教授指導開發了基因重整繁衍法，大量產生最少提示數盤面。

本篇論文研究候選數特性，以集合邏輯的觀念，開發新的解題法，簡化解題的架構及方法，減少解題所需時間；進而改良基因重整繁衍法，使盤面的產生更加快速。最後再根據盤面特徵，快速的比對新產生的盤面是否已重複。

Sudoku has been popular for several years around the world. There have been many algorithms built for solving Sudoku, and among them, candidates algorithms remain the most popular nowadays. Also, researchers have long been focusing on the generators of puzzles. For instance, Lin & Lin (2008) proposed the “genes restructuring” algorithm which was able to generate a large amount of Minimum Sudoku puzzles.

This paper aims to study the properties of Sudoku candidates. Then it suggests a new algorithm based on logic and sets principle as well as simplifies the process of solving puzzles and shortens the solving time. In addition, this paper improves the “genes restructuring” algorithm to make the puzzles generating faster. Finally, it checks the newly-generated puzzles to verify if they are duplicated ones.