In Search of Dotless Kropki Puzzle Solution

Andri Purnama Ramadan

Abstract


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.

Keywords


Kropki; Latin Square; Puzzle

Full Text:

PDF

References


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




DOI: http://dx.doi.org/10.12962/j24775401.v10i1.17123

Refbacks

  • There are currently no refbacks.



View My Stats


Creative Commons License
International Journal of Computing Science and Applied Mathematics by Pusat Publikasi Ilmiah LPPM, Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/ijcsam.