THE SMY INVARIANT AND THE MDSL CONJECTURE IN THE CII ALGORITHM FOR SOLVING SUDOKU PUZZLES
Keywords:
Boolean Groebner bases, Sudoku puzzles, Inoue algorithm, CII algorithm.DOI:
https://doi.org/10.17654/0972096022013Abstract
The Inoue algorithm is a fundamental method for solving Sudoku puzzles mathematically by Boolean Groebner bases. The CII algorithm is a refined form of the Inoue algorithm and is closely related to human “Try and Error” method for solving Sudoku puzzles. Thus, it has been successfully applied to the evaluation of difficulty level of the puzzles.
In this paper, we will present three results concerning CII algorithm. The first one is the development of a new method called “nakano9” which executes the CII algorithm, mainly for the purpose of applying to MDSL conjecture. The second one is the definition of the SMY invariant of Sudoku puzzles in terms of CII algorithm, and we confirm that it is an excellent mathematical indicator of difficulty level of Sudoku puzzles. We thirdly propose the MDSL conjecture based on experiments, which says that, in the Inoue algorithm, every Sudoku puzzle with a unique solution has a solution of depth smaller than or equal to 3. This is a rather surprising conjecture since it claims that, even if how difficult the puzzle is, it can be solved within 3 steps if a suitable cell and value are selected at branch points.
Received: June 19, 2022
Accepted: July 1, 2022
References
W. Bosma, J. J. Cannon, C. Fieker and A. Steel, eds., Handbook of Magma functions, http://magma.maths.usyd.edu.au/magma/, accessed: 10 April 2022.
D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Third ed., Springer, New York, 2007.
K. Gohnai, Number Placement Puzzles (Basic, Middle, High, SuperHigh, Hard, SuperHard, UltraHard), Kosaido Publishing Co., Tokyo, 2008 (in Japanese).
A. Inkala, AI Sudoku, www.aisudoku.com/en/, accessed: 10 April 2022.
S. Inoue, Efficient singleton set constraint solving by Boolean Gröbner bases, Communications of JSSAC 1 (2012), 27-37.
S. Inoue and Y. Sato, A mathematical hierarchy of Sudoku puzzles and its computation by Boolean Groebner bases, LNCS 8884, Springer, 2014, pp. 88-98.
T. Nakano, K. Arai and H. Watanabe, On the Inoue invariants of the puzzles of Sudoku type, Communications of JSSAC 2 (2016), 1-14.
T. Nakano, Y. Maruyama and S. Ohki, On the mathematical evaluation of difficulty level of Sudoku puzzles by Boolean Groebner bases, Far East J. Appl. Math. 106 (2020), 43-70.
T. Nakano, S. Minami, S. Harikae, K. Arai, H. Watanabe and Y. Tonegawa, On the Inoue invariants of the puzzles of Sudoku type II, Bulletin of JSSAC 24 (2018), 77-90.
T. Nakano and Y. Tonegawa, Introduction to Boolean Groebner bases and their applications to puzzles of Sudoku type, J. Algebra Appl. Math. 12 (2014), 1-31.
Y. Sato, S. Inoue, A. Suzuki, K. Nabeshima and K. Sakai, Boolean Gröbner bases, Journal of Symbolic Computation 46 (2011), 622-632.
D. Tarek, http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539. html, accessed: June 6, 2022.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
This work is licensed under a Creative Commons Attribution 4.0 International License.
____________________________
Licensing Terms:
This work is published by Pushpa Publishing House and is subject to the following conditions:
Attribution: You must credit Pushpa Publishing House as the original publisher. Include the publication title and author(s) if applicable.
No Derivatives: Modifying the work or creating derivative works is not permitted without prior written permission.
For more information or permissions beyond the scope of this license, contact Pushpa Publishing House.
Publication count: 
Google h-index: 
Downloads: 