Reducing the generalised Sudoku problem to the Hamiltonian cycle problem

AKCE International Journal of Graphs and Combinatorics

关键词: Sudoku;    NP-complete;    Reduction;    Hamiltonian cycle problem;   

DOI  :  10.1016/j.akcej.2016.10.001

来源: DOAJ

【 摘 要 】

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(N3) 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.

【 授权许可】

Unknown