POLYNOMIAL 3-SAT REDUCTION OF SUDOKU PUZZLE

Deepika Rai, N.S. Chaudhari, Maya Ingle

Abstract


3-Satisfiability (3-SAT) reduction has always been remarkable asset in proving the NP-Completeness of other problems. 3-SAT problem is an NP-Complete problem used as a starting point to prove the hardness of other problems. Therefore, every NP-Complete problem can be reduced into 3-SAT that can be solved by a SAT solver. In this perspective, determining 3-SAT reduction from Sudoku Puzzle of size (n x n) is very helpful to obtain the solution of Sudoku Puzzle using SAT solver. Thus, we have obtained polynomial 3-SAT reduction of Sudoku Puzzle (n x n) as well as total number of 3-SAT clauses and new variables generated in 3-SAT reduction are 4 [n4 – 2n2 + m] and 2 [n2 {n2 + n – 6} + m] respectively.

Keywords


3-SAT, Sudoku Puzzle, NP-Complete Problem, SAT solver, Polynomial Time

Full Text:

PDF

References


Marques Silva J., Malik S., “Propositional SAT Solving”, In: Clarke E., Henzinger T., Veith H., Bloem R. (eds) Handbook of Model Checking, Springer, Cham, pp. 247-275, 2018.

Claessen, Koen, N. Een, M. Sheeran, N. Sorensson, “SAT-Solving in Practice”, 9th IEEE International Conference on Discrete Event Systems, pp. 61-67, 2008.

A.K. Maji, R.K. Pal, “Sudoku Solver using Minigrid Based Backtracking”, IEEE International Conference on Advance Computing (IACC), pp. 36-44, 2014.

Perez, Meir, TshilidziMarwala, “Stochastic Optimization Approaches for Solving Sudoku”, Archives of Neural and Evolutionary Computing, Cornell University Library, 2008.

Deng, Xiu Qin, Yong Da Li., “A Novel Hybrid Genetic Algorithm for Solving Sudoku Puzzles”, Springer Journal of Optimization Letters, Vol. 7, No. 2, pp. 241-257, 2013.

Bartlett, Andrew C., Amy N. Langville, “An Integer Programming Model for the Sudoku Problem”, Journal of Online Mathematics and its Applications, Vol. 8, Article ID 1798, 2008.

Ines Lynce, Joel Ouaknine, “Sudoku as a SAT Problem”, Proceedings of 9th International Symposium on Artificial Intelligence and Mathematics, 2006.

Prakash C.Sharma and Narendra S. Chaudhari, “A Graph Coloring Approach for Channel Assignment in Cellular Network via Propositional Satisfiability”, International Conference on Emerging Trends in Networks and Computer Communications (ETNCC) at Udaipur, pp. 23-26, 2011.

N.Dahale, N.S.Chaudhari, M. Ingle, “Determining Vertex Cover Using Polynomial Encoding of 3sat”, VNSGU Journal of Science and Technology, Vol. 4, No. 1, pp. 197-204, 2015.

Prakash C. Sharma and Narendra S. Chaudhari, “Polynomial 3-SAT Encoding for K-Colorability of Graph”, Evolution in Networks and Computer Communications-A Special Issue from IJCA, Article 4, No. 1, pp. 19-24, 2011.

Tovey, Craig A., “A simplified NP-complete satisfiability problem”,Discrete Applied Mathematics, Elsevier, Vol. 8, No. 1,pp. 85-89, 1984.

N. Chandrasekaran, K.L.P Mishra, “Theory of Computer Science”, PHI Learning publishing, 3rd edition, 2011.

Felgenhauer, Bertram, Frazer Jarvis, “Mathematics of Sudoku-I”, Mathematical Spectrum, Vol. 39, No. 1, pp. 15-22, 2006.

G. Kendall, A.J. Parkes, K. Spoerer, “A Survey of NP-Complete Puzzles”, International Computer Games Association (ICGA) Journal, Vol.31, No. 1, pp. 13-34, 2008




DOI: https://doi.org/10.26483/ijarcs.v9i3.6096

Refbacks

  • There are currently no refbacks.




Copyright (c) 2018 International Journal of Advanced Research in Computer Science