Sudoku is one of those NP-Complete problems that brute force solutions have a problem with. Consider a board with a single blank space, we would have to work through 9 possibilities to find the right answer. For two blank spaces, we would work through 9 possibilities for the first space, and then for each of those possibilities, 9 for the second.
This simplifies to a time complexity of O(n^m) where n is the number of possibilities for each square (9 in normal Sudoku) and m is the number of blank spaces. A hard Sudoku problem with 50 blank spaces would take about 5.15 * 1047 computations, which would take longer than the age of the universe to solve with a decent computer.
This is where artificial intelligence (AI) comes into play. Think of AI less as a Skynet robot and more as a set of hacks to solve exponential problems like Sudoku. Code for this post can be found here.
Continue reading “Programming #10: AI Sudoku”