zbMATH — the first resource for mathematics

Reducing the generalised Sudoku problem to the Hamiltonian cycle problem. (English) Zbl 1354.05018
Summary: 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.
MSC:
 05B15 Orthogonal arrays, Latin squares, Room squares 05C45 Eulerian and Hamiltonian graphs 05C38 Paths and cycles
Concorde; LKH
Full Text:
References:
 [1] Yato, T.; Seta, T., Complexity and completeness of finding another solution and its application to puzzles, IEICE Trans. Fundam. Electron., E86-A, 5, 1052-1060, (2003) [2] H. Simonis, Sudoku as a constraint problem, In: CP Workshop of Modeling and Reformulating Constraint Satisfaction Problems, 2005, pp. 13-27. [3] I. Lynce, J. Ouaknine, Sudoku as a SAT Problem. In: Proceedings of the 9th Symposium on Artificial Intelligence and Mathematics, 2006. [4] Bartlett, A.; Chartier, T. P.; Langville, A. V.; Rankin, T. D., An integer programming model for the sudoku problem, J. Online Math. Appl., 8, (2008), Article ID 1798 [5] Karp, R. M., Reducibility among combinatorial problems, (1972), Springer New York · Zbl 0366.68041 [6] Dewdney, A. K., Linear transformations between combinatorial problems, Int. J. Comput. Math., 11, 91-110, (1982) · Zbl 0478.68071 [7] Creignou, N., The class of problems that are linearly equivalent to satisfiability or a uniform method for proving np-completeness, Lect. Notes. Comput. Sci., 145, 111-145, (1995) · Zbl 0874.68127 [8] Filar, J. A.; Haythorpe, M.; Taylor, R., Linearly-growing reductions of karp’s 21 NP-complete problems, Numer. Algebra Control Optim., (2016), in press [9] Filar, J. A.; Haythorpe, M., A linearly-growing conversion from the set splitting problem to the directed Hamiltonian cycle problem, (Optimization and Control Methods in Industrial Engineering and Construction, (2014)), 35-52 [10] Ejov, V.; Haythorpe, M.; Rossomakhine, S., A linear-size conversion of HCP to 3HCP, Australas. J. Combin., 62, 1, 45-58, (2015) · Zbl 1321.05144 [11] Chalaturnyk, A., A fast algorithm for finding Hamilton cycles, (2008), University of Manitoba, (Masters thesis) [12] Baniasadi, P.; Ejov, V.; Filar, J. A.; Haythorpe, M.; Rossomakhine, S., Deterministic “snakes and ladders” heuristic for the Hamiltonian cycle problem, Math. Program. Comput., 6, 1, 55-75, (2014) · Zbl 1301.05326 [13] D.L. Applegate, R.B. Bixby, V. Chavátal, W.J. Cook, Concorde TSP Solver, 2015. http://www.tsp.gatech.edu/concorde/index.html (Accessed Jan 20, 2016). [14] Helsgaun, K., An effective implementation of lin-kernighan traveling salesman heuristic, European J. Oper. Res., 126, 106-130, (2000) · Zbl 0969.90073 [15] A. Johnson, Quasi-linear reduction of Hamiltonian Cycle Problem (HCP) to Satisfiability Problem (SAT). IP.com Disclosure Number IPCOM000237123D, 2014. [16] Haythorpe, M., Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles, Electron. J. Graph Theory Appl., 4, 1, 18-25, (2016) [17] M. Haythorpe, FHCP Challenge Set., 2015. http://fhcp.edu.au/fhcpcs. [18] Newcombe, A., Investigating Hamilton cycles using logistic regression, (2015), (Honours thesis) [19] Filar, J. A.; Haythorpe, M.; Rossomakhine, S., A new heuristic for detecting non-Hamiltonicity in cubic graphs, Comput. Oper. Res., 64, 283-292, (2015) · Zbl 1349.90813 [20] G. Royle, Minimum Sudoku, 2005. http://staffhome.ecm.uwa.edu.au/ 00013890/sudokumin.php (Accessed 20 January 2016). [21] McGuire, G.; Tugemann, B.; Civario, G., There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration, Exp. Math., 23, 2, 190-217, (2014) · Zbl 1296.05008 [22] B. Knockel, Sudoku Generator, 2013. http://www.mathworks.com/matlabcentral/fileexchange/28168-sudoku-generator (Accessed Sep 16, 2016).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.