On Specific 17-clue Sudoku Puzzles

Article type: Research Article

Authors: Lin, Hung-Hsuan¹ | Wu, I-Chen¹ | Wei, Tinghan¹

Affiliations: Hsinchu, Taiwan

Note: [1] Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan. Email: stanleylin@aigames.nctu.edu.tw, icwu@aigames.nctu.edu.tw, ting@aigames.nctu.edu.tw.

Abstract: Since Sudoku was invented, it has been interesting to find Sudoku puzzles with the minimum number of clues. Royle collected 49,151 17-clue Sudoku puzzles between 2005 and 2009, each of which is not isomorphic to any other, and McGuire claimed in 2012 that no 16-clue Sudoku puzzle exists. Since 2009, no new 17-clue Sudoku puzzles have been found. This paper proposes an algorithm to find 17-clue Sudoku puzzles based on the number of clues in the topmost 9x3 cells, which is called a top-block. Using this algorithm, we prove that (1) no 17-clue puzzles exist of which the top-block has fewer than three clues and (2) precisely 95 17-clue puzzles exist of which the top-block has three and only three clues. Moreover, we compared these 95 puzzles to the 49,151 collected 17-clue Sudoku puzzles and found that these 95 puzzles are already collected by Royle. Thus, a conjecture from this paper is that most of the 17-clue Sudoku puzzles have been found.

DOI: 10.3233/ICG-2013-36302

Journal: ICGA Journal, vol. 36, no. 3, pp. 131-138, 2013