In Search of Dotless Kropki Puzzle Solution
Kata Kunci:
Kropki, Latin Square, PuzzleAbstrak
Searching all possible solution and finding the minimum number of clues to make uniquely solvable puzzle always been a natural question for puzzle enthusiast. However, the attempt usually provide that as difficult task. In this paper, we attempt to search the solution of Kropki puzzle without dot clues given with graph theory approach, which resulted in a conjectures involving the planarity of graph and cyclicity of latin square.Referensi
M.Haythorpe, "Reducing the Generalised Sudoku Problem to the Hamiltonian Cycle Problem," AKCE International Journal of Graphs and Combinatorics, vol. 13, issue 3, pp. 272-282, 2016. DOI: https://doi.org/10.1016/j.akcej.2016.10.001
A.K.Maji, S.Jana, and R.K.Pal, "An Algorithm for Generating only Desired Permutations for Solving Sudoku Puzzle," Procedia Technology, vol. 10, pp. 392-399, 2013. DOI: https://doi.org/10.1016/j.protcy.2013.12.375
E.D.Demaine, F.Ma, A.Schvartzman, E.Waingarten, and S.Aaronson, "The Fewest Clues Problem," Theoretical Computer Science, vol. 748, pp. 28-39, 2018. DOI: https://doi.org/10.1016/j.tcs.2018.01.020
D.Berend, "On the number of Sudoku squares," Discrete Mathematics, vol. 341, issue 11, pp. 3241-3248, 2018. DOI: https://doi.org/10.1016/j.disc.2018.08.005
G.Mcguire, T.Bastian, and C.Gilles, "There is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration," Experimental Mathematics, vol. 23, issue 2, pp. 190-217, 2014. DOI: https://doi.org/10.48550/arXiv.1201.0749
V.Dabbaghian and T.Wu, "Recursive Construction of Non-cyclic Pandiagonal Latin Squares," Discrete Mathematics, vol. 313, issue 23, pp. 2835-2840, 2013. DOI: https://doi.org/10.1016/j.disc.2013.08.020
R.W.Hung, C.F.Li, J.S.Chen, and Q.S.Su, "The Hamiltonian connectivity of rectangular supergrid graphs," Discrete Optimization, vol. 26, pp. 41-65, 2017. DOI: https://doi.org/10.1016/j.disopt.2017.06.001
M.SRahman, M.Kaykobad, and J.S.Firoz, "New Sufficient Conditions for Hamiltonian Paths," The Scientific World Journal, vol. 2014, Article ID 743431, 6 pages, 2014. DOI: https://doi.org/10.1155/2014/743431
J.Li, G.Su, H.Shi, F.Liu, "On sufficient conditions for a graph to be $(k)$-path-coverable, $(k)$-edge-hamiltonian, Hamilton-connected, traceable and $(k^{-})$-independent," Open Journal of Discrete Applied Mathematics, vol. 3, pp. 66-76, 2020 DOI: {http://dx.doi.org/10.30538/psrp-odam2020.0045
G.H.Fan, "New Sufficient Conditions for Cycles in Graphs," Journal of Combinatorial Theory, Series B, vol. 37, issue 3, pp. 221-227, 1984. DOI: https://doi.org/10.1016/0095-8956(84)90054-6
W.Klotz, "A Constructive Proof of Kuratowski's Theorem,"Ars Combinatoria -Waterloo then Winnipeg-, vol. 28, pp. 51-54, 1989. Available: https://www.researchgate.net/publication/256078009_A_constructive_proof_of_Kuratowski's_theorem
