An In Depth Analysis of Sudoku with Focus in Integer and Constraint Programming
Open Access
Author:
Thein, Michael William
Graduate Program:
Industrial Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
None
Committee Members:
Dr Paul Griffin, Thesis Advisor/Co-Advisor
Keywords:
Sudoku Integer Programming Constraint Programming
Abstract:
We analyze sudoku in detail. We study sudoku as it pertains to computational complexity, graph coloring, and various programming methods that can be used to solve sudoku. We construct integer and constraint programs to solve sudoku problems. We conduct empirical experiments using these programs. Our results exhibit constant solve times for our integer program and varied solve times for our constraint program depending on difficulty. For easier sudokus, constraint programming performs significantly faster,but as difficulty increases, our integer program exhibited faster solve times. Additionally, we applied a heuristic. When combined with a heuristic, the constraint program solve times were significantly improved. The solve times were drastically better than those of our integer program for easy, medium, and hard difficulty, and were only slightly worse for evil difficulty. We tested to see how solve times reduced when more information is provided to our constraint solver. We observe an exponential decay function in solve times as more cells were filled in. Finally, we present future research that we wish to conduct.
