Sudoku Algorithm

This paper proposes a solution-yielding linear time algorithm to NP-complete Sudoku, to which no polynomial time algorithm has been proposed. The proposed algorithm is performed on blocks in the descending order of the number of clues they contain. It firstly determines all numbers that could possibly occur in the blank rows and columns of each block. By deriving an intersecting value of corresponding rows and columns, it assigns the final number for each blank. When tested on the traditional Sudoku, the proposed algorithm has succeeded in obtaining the solution through performance of 9 times, the exact number of the blocks. Test results on modified Jigsaw Sudoku (9 blocks) and Hypersudoku (13 blocks) also show its success in deriving the solutions by execuring 9 and 13 times respectively. Accordingly, this paper proves that the Sudoku problem is in fact P-problem.