Archive for March, 2010
In Computing science artificial intelligence terms, the game of Sudoku is a constraint satisfaction problem. Constraint satisfaction problems are nice in the regard that there are some very nice heuristics that lead to an easy algorithm to solve them. On the other hand, constraint satisfaction problems with a large problem domain may take an inordinate amount of time to solve.
Sudoku consists of a 9×9 grid, with each grid cell having a possible 9 different values. If we ignore all the constraints, this gives a possible 9^81 boards (1.9662705 × 10^77). Say we can check one-hundred trillion boards a second (100,000,000,000), it would still take ((9^81)/100000000000)/(31556926) = 6.23 × 10^58 years to iterate over all possible combinations! Clearly randomly generating boards and checking if the constraints are fulfilled is not a realistic solution.
Read the rest of this entry »