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.

Boolean Groebner bases, Sudoku puzzles, Inoue algorithm, CII algorithm.

Received: June 19, 2022; Accepted: July 1, 2022; Published: August 17, 2022

How to cite this article: Tetsuo Nakano, Miku Shindou, Naoki Mikoshiba and Tsukasa Yoshihara, The SMY invariant and the MDSL conjecture in the CII algorithm for solving Sudoku puzzles, Far East Journal of Applied Mathematics 114 (2022), 25-48. http://dx.doi.org/10.17654/0972096022013

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] 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.
[2] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Third ed., Springer, New York, 2007.
[3] K. Gohnai, Number Placement Puzzles (Basic, Middle, High, SuperHigh, Hard, SuperHard, UltraHard), Kosaido Publishing Co., Tokyo, 2008 (in Japanese).
[4] A. Inkala, AI Sudoku, www.aisudoku.com/en/, accessed: 10 April 2022.
[5] S. Inoue, Efficient singleton set constraint solving by Boolean Gröbner bases, Communications of JSSAC 1 (2012), 27-37.
[6] 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.
[7] T. Nakano, K. Arai and H. Watanabe, On the Inoue invariants of the puzzles of Sudoku type, Communications of JSSAC 2 (2016), 1-14.
[8] 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.
[9] 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.
[10] 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.
[11] Y. Sato, S. Inoue, A. Suzuki, K. Nabeshima and K. Sakai, Boolean Gröbner bases, Journal of Symbolic Computation 46 (2011), 622-632.
[12] D. Tarek, http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539. html, accessed: June 6, 2022.