Searching for Sudoku puzzle problems with a small number hints using the Metropolis sampler.
-
- FURUKAWA Yu
- Graduate School of Science and Technology, Meijo University
-
- YAMAMOTO Osami
- Faculty of Science and Technology, Meijo University
Bibliographic Information
- Other Title
-
- メトロポリスサンプラーを用いたヒント数の少ない数独問題の探索
Abstract
<p>Sudoku is a puzzle with $9\times9$ cells where some numbers are given as hints. Although the puzzles tend to be difficult when small number of hints are given, we can solve any Sudoku puzzles in a reasonable time using backtracking. Contrarily, it is difficult to make a Sudoku puzzle with small number of hints because each puzzle should have only one solution. This paper presents a greedy algorithm for generating Sudoku puzzles with small number of hints by adding hints one by one starting from the hint less pattern. Employing a Metropolis sampler, we chose the optimal hints which reduced the number of solutions faster. Using the algorithm, we were able to obtain a puzzle with nineteen hints in 65 minutes and 19 seconds using a PC with Intel(R) Xeon(R) E3-1225 V2 3.2 GHz. Repeating the method fifteen times, we were able to obtain two Sudoku puzzles with nineteen hints.</p>
Journal
-
- Proceedings of the Annual Conference of JSAI
-
Proceedings of the Annual Conference of JSAI JSAI2020 (0), 4C2GS1301-4C2GS1301, 2020
The Japanese Society for Artificial Intelligence
- Tweet
Details 詳細情報について
-
- CRID
- 1390848250119719168
-
- NII Article ID
- 130007857214
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- CiNii Articles
-
- Abstract License Flag
- Disallowed