Reducing the generalised Sudoku problem to the Hamiltonian cycle problem

    Research output: Contribution to journalArticlepeer-review

    1 Citation (Scopus)

    Abstract

    The generalised Sudoku problem with N symbols is known to be NP-complete, and hence is equivalent to any other NP-complete problem, even for the standard restricted version where N is a perfect square. In particular, generalised Sudoku is equivalent to the, classical, Hamiltonian cycle problem. A constructive algorithm is given that reduces generalised Sudoku to the Hamiltonian cycle problem, where the resultant instance of Hamiltonian cycle problem is sparse, and has O(N 3 ) vertices. The Hamiltonian cycle problem instance so constructed is a directed graph, and so a (known) conversion to undirected Hamiltonian cycle problem is also provided so that it can be submitted to the best heuristics. A simple algorithm for obtaining the valid Sudoku solution from the Hamiltonian cycle is provided. Techniques to reduce the size of the resultant graph are also discussed.

    Original languageEnglish
    Pages (from-to)272-282
    Number of pages11
    JournalAKCE International Journal of Graphs and Combinatorics
    Volume13
    Issue number3
    DOIs
    Publication statusPublished - 2016

    Fingerprint Dive into the research topics of 'Reducing the generalised Sudoku problem to the Hamiltonian cycle problem'. Together they form a unique fingerprint.

    Cite this