Reducing the generalised Sudoku problem to the Hamiltonian cycle problem

DOI10.1016/J.AKCEJ.2016.10.001zbMATH Open1354.05018arXiv1603.03019OpenAlexW2963317769MaRDI QIDQ504159FDOQ504159

Authors: Michael Haythorpe 

Publication date: 25 January 2017

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1603.03019

Recommendations

• Solving the Hamiltonian cycle problem using symbolic determinants
• Solution of two problems of P. Erdős concerning Hamiltonian cycles
• The structure of reduced Sudoku grids and the Sudoku symmetry group
• On two problems regarding the Hamiltonian cycle game
• The Hamilton circuit problem on grids
• Publication:4729825
• Hamiltonianicity of the towers of Hanoi problem
• An analogue of Ryser's theorem for partial Sudoku squares

zbMATH Keywords

reductionHamiltonian cycle problemSudokuNP-completenes

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Orthogonal arrays, Latin squares, Room squares (05B15) Paths and cycles (05C38)

Cites Work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Title not available (Why is that?)
• There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• A new heuristic for detecting non-Hamiltonicity in cubic graphs
• Linearly-growing reductions of Karp's 21 NP-complete problems
• A Linear-size Conversion of HCP to 3HCP
• Linear time transformations between combinatorial problems
• Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles
• Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem

Uses Software

• LKH
• Concorde

This page was built for publication: Reducing the generalised Sudoku problem to the Hamiltonian cycle problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q504159)