1. Introduction
  2. Sudoku Explained
  3. How to Think About It
  4. Getting Started
  5. A First Approach-
    Brute Force
  6. Brute Force in Action
  7. Improving on Brute Force
  8. Better Brute Force
  9. Backtracking Search
  10. Backtracking with MRV
  11. Attack of the Samurai
  12. Strategize
  13. Backtracking MRV with
    Unique Constraint
  14. Backtracking MRV with
    Unique Constraint part 2
  15. Conclusion
 Previous Page Brute Force in Action Next Page



(NOTE: You should see a java applet above; if you do not, you lack either luck or Java 1.5)

Wow. That's awful. Really awful. And painfully slow.

How slow though? Note that there are 17 filled squares, and 64 unfilled squares. Each of these can take on a value of 1 through 9, giving a total of 11,790,184,577,738,583,171,520,872,861,412,518,665,678,211,592,275,841,109,096,961 = 1.179*10^61 possible combinations. If we were to take a million 100 GHz computers each with 1,000,000 CPU cores, that could determine if a sudoku state was valid in a single clock cycle, and if we were to go back to shortly after the big bang, by now we would have calculated ~10^40 of the possible states in this puzzle. Meaning the entire calculation would take about 10^20 times the current age of the universe. You will be waiting a very very very long time for that to finish.

So, let's try something less awful.

Special Thanks to Peter Norvig for an interesting talking point. http://norvig.com/sudoku.html
Previous Page Brute Force in Action Next Page