PROPOSAL

PRESENTATION

REPORT

CODE

Using stochastic search methods to find solutions to Constraing Satisfaction Problems (CSPs) has been reasonably successful in the recent years, with the deterministic search methods performing worse in many combinatorially hard problems. This motivated us to test this "superiority" of Stochastic Search methods over Deterministic Search methods. In this project, we implement Progressive Stochastic Search and Incremental Progressive Stochastic Search as methods to solve Sudoku puzzles of order-2,3 and 4. The results show that these methods do converge to correct solutions, building heuristics during the process, without exploiting any problem-specific standard solving methods. The timings show that deterministic methods have an extremely fast convergence, solving order-2 3 puzzles in time less than 20 ms. On the other hand, PSS solves order-2 puzzles in about 11.554 microseconds, order-3 puzzles in about 545.850 ms, easy, intermediate hard order-4 puzzles in about 2, 12 and 30 minutes respectively.

A Sudoku Puzzle...	...and its solution numbers marked in red Source: Wikipedia

References

1. Bryan Chi-ho Lam and Ho-fung Leung, 2003. Progressive Stochastic Search for Solving Constraint Satisfaction Problems. Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’03) 1082-3409/03, Pages 487-491 bibtex
2. Rhydian Lewis, 2007. On the Combination of Constraint Programming and Stochastic Search. The Sudoku Case Proceedings of the 4th international conference on Hybrid metaheuristics. bibtex
3. Helmut Simonis, 2005, Sudoku as a Constraint Problem, IC-Parc, Imperial College, London Abstract
4. Solving Every Sudoku Puzzle by Peter Norvig
5. http://en.wikipedia.org/wiki/Sudoku