{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T09:39:28Z","timestamp":1770457168489,"version":"3.49.0"},"reference-count":18,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T00:00:00Z","timestamp":1594857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17K17725"],"award-info":[{"award-number":["17K17725"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A Sudoku puzzle often has a regular pattern in the arrangement of initial digits and it is typically made solvable with known solving techniques called strategies. In this paper, we consider the problem of generating such Sudoku instances. We introduce a rigorous framework to discuss solvability for Sudoku instances with respect to strategies. This allows us to handle not only known strategies but also general strategies under a few reasonable assumptions. We propose an exact method for determining Sudoku clues for a given set of clue positions that is solvable with a given set of strategies. This is the first exact method except for a trivial brute-force search. Besides the clue generation, we present an application of our method to the problem of determining the minimum number of strategy-solvable Sudoku clues. We conduct experiments to evaluate our method, varying the position and the number of clues at random. Our method terminates within 1 min for many grids. However, as the number of clues gets closer to 20, the running time rapidly increases and exceeds the time limit set to 600 s. We also evaluate our method for several instances with 17 clue positions taken from known minimum Sudokus to see the efficiency for deciding unsolvability.<\/jats:p>","DOI":"10.3390\/a13070171","type":"journal-article","created":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T10:54:46Z","timestamp":1594896886000},"page":"171","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Exact Method for Generating Strategy-Solvable Sudoku Clues"],"prefix":"10.3390","volume":"13","author":[{"given":"Kohei","family":"Nishikawa","sequence":"first","affiliation":[{"name":"Graduate School of Informatics and Engineering, University of Electro-Communications, Tokyo 182-8585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takahisa","family":"Toda","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics and Engineering, University of Electro-Communications, Tokyo 182-8585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,16]]},"reference":[{"key":"ref_1","unstructured":"Davis, T. (2020, May 26). The Mathematics of Sudoku. Available online: http:\/\/www.geometer.org\/mathcircles\/sudoku.pdf."},{"key":"ref_2","unstructured":"Zama, S., and Sasano, I. (2020, June 17). Technical Report 1, IPSJ SIG Technical Report, 2016-G1-35. (In Japanese)."},{"key":"ref_3","unstructured":"Maeda, K., and Okuno, H. (2008, January 13\u201315). Design and Implementation of Sudoku Puzzle Constructing Support System. Proceedings of the 70th National Convention of IPSJ, Tsukuba, Japan. (In Japanese)."},{"key":"ref_4","unstructured":"Stuart, A.C. (2020, June 17). Sudoku Creation and Grading. Available online: https:\/\/www.sudokuwiki.org\/Sudoku_Creation_and_Grading.pdf."},{"key":"ref_5","unstructured":"Royle, G.F. (2020, May 26). A Collection of 49,151 Distinct Sudoku Configurations with 17entries. Available online: https:\/\/staffhome.ecm.uwa.edu.au\/~00013890\/sudokumin.php."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1080\/10586458.2013.870056","article-title":"There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration","volume":"23","author":"McGuire","year":"2014","journal-title":"Exp. Math."},{"key":"ref_7","unstructured":"Tramura, N. (2020, May 26). Sugar: A SAT-Based Constraint Solver. Available online: http:\/\/bach.istc.kobe-u.ac.jp\/sugar\/."},{"key":"ref_8","unstructured":"Tamura, N., and Banbara, M. (2020, June 17). Sugar: A CSP to SAT Translator Based on Order Encoding. Available online: http:\/\/bach.istc.kobe-u.ac.jp\/papers\/pdf\/cpai06.pdf."},{"key":"ref_9","unstructured":"E\u00e9n, N., and S\u00f6rensson, N. (2020, May 26). The MiniSat Page. Available online: http:\/\/minisat.se\/."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Giunchiglia, E., and Tacchella, A. (2004). An Extensible SAT-solver. Theory and Applications of Satisfiability Testing, Springer.","DOI":"10.1007\/b95238"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/TG.2019.2917792","article-title":"Procedural Puzzle Generation: A Survey","volume":"12","author":"Haahr","year":"2020","journal-title":"IEEE Trans. Games"},{"key":"ref_12","unstructured":"Contributors, W. (2020, June 17). Sudoku Solving Algorithms\u2014Wikipedia The Free Encyclopedia. Available online: https:\/\/en.wikipedia.org\/wiki\/Sudoku_solving_algorithms."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Mantere, T., and Koljonen, J. (2007, January 25\u201328). Solving, rating and generating Sudoku puzzles with GA. Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore.","DOI":"10.1109\/CEC.2007.4424632"},{"key":"ref_14","unstructured":"Knuth, D.E. (2019). The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links, Pearson Education."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Zambon, G. (2015). Sudoku Programming with C, Apress. [1st ed.].","DOI":"10.1007\/978-1-4842-0995-0"},{"key":"ref_16","unstructured":"Boothby, T., Svec, L., and Zhang, T. (2020, June 17). Generating Sudoku Puzzles as an Inverse Problem. Available online: https:\/\/sites.math.washington.edu\/~morrow\/mcm\/team2306.pdf."},{"key":"ref_17","unstructured":"Gebser, M. (2020, June 17). gen sudoku.gringo. Available online: https:\/\/asparagus.cs.uni-potsdam.de\/encoding\/show\/id\/12739."},{"key":"ref_18","first-page":"1811","article-title":"Rating and Generating Sudoku Puzzles Based on Constraint Satisfaction Problems","volume":"8","author":"Fatemi","year":"2014","journal-title":"Int. J. Comput. Inf. Eng."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/7\/171\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:49:08Z","timestamp":1760176148000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/7\/171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,16]]},"references-count":18,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2020,7]]}},"alternative-id":["a13070171"],"URL":"https:\/\/doi.org\/10.3390\/a13070171","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,16]]}}}