Main Article Content

Deepika Rai
N.S. Chaudhari
Maya Ingle


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.


Download data is not yet available.

Article Details



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