POLYNOMIAL 3-SAT REDUCTION OF SUDOKU PUZZLE

Abstract

3Satisfiability (3SAT) reduction has always been remarkable asset in proving the NPCompleteness of other problems. 3SAT problem is an NPComplete problem used as a starting point to prove the hardness of other problems. Therefore, every NPComplete problem can be reduced into 3SAT that can be solved by a SAT solver. In this perspective, determining 3SAT 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 3SAT reduction of Sudoku Puzzle (n x n) as well as total number of 3SAT clauses and new variables generated in 3SAT reduction are 4 [n4 2n2 + m] and 2 [n2 {n2 + n 6} + m] respectively.