SONG

---

THE AMAZING WORLD OF SUDOKU!!!

--TYPICAL INITIAL DESIGN PROCESS, TO VERIFY THE NUMBER OF POSSIBLE SUDOKU SOLUTION--

1. The programmer, begins the design process thinking his computer is so fast, that a fancy algorithm is not needed to check a simple 9^81 grid. It couldn't take more than a few minutes, TOPS; could it? So, the programmer checks:

         111111111 NO,     111111111 NO,     111111111
         111111111 then    111111111 and     111111111
         111111111 changes 111111111 then    111111111  NO,
         111111111 the 1,  111111111 the 2,  111111111  ETC, ETC, ETC- 9^81 times,
         111111111 to a 2, 111111111 to a 3. 111111111  to check all the possible
         111111111 like    111111111         111111111  combinations...
         111111111 so.     111111111         111111111
         111111111         111111111         111111111
         111111111         111111112         111111113

2. The programmer writes a program, using fairly tight code, saving as much processing time as he can muster. He figures that the program shouln't take very long to run, because he's sure he wrote very tight code.
3. The program runs for more than a few minutes; so the programmer decides to check to see how long, this program would actually take to run to completion. A quick check reveals that it would take----[CATCH YOUR BREATH]----511,071,019,291,122,369,865,290,488,114,820,175,545,447,748,536,772,255,768,357,930 years to complete.[Can you even fathom, how long that is?? OK, Let's say that the UNIVERSAL PHASE(how long it is, in between, the beginning of an old universe, to the beginning of a new universe) were 1 trillion years(scientists would probably consider this a very conservative estimate). The amount of time this slow algorithm would take, is: Step 1: One UNIVERSAL PHASE(a trillion years); Step 2: Step 1, a trillion times; Step 3: Step 2, a trillion times; Step 4: Step 3, a trillion times; Step 5: Step 4, a trillion times; Step 6:(and believe it, or not, by far the HUGEST step) Step 5, a measly 51.1 times...]
4. After falling out of his chair, and all but crapping his pants; the programmer calms down after a day, or two, and he decides that there must be a faster algorithm.
5. So, the programmer says to himself, "SELF": "What if I started from the front-end, eliminating candidates from the get-go." Then, the programmer tries: 1.......YES ,then 11.....NO, ok 12.....YES, 121....NO, 122....NO, 123....YES, 1231.....NO, 1232....NO, 1233....NO, 1234....YES........and so on, and so on, until eventually all 9^81 combinations would be ruled, in or out... without having to check anywhere near all 9^81 combinations, one at a time.
6. Certainly, this will go much faster! The programmer pats himself on the back, confident that he'll surely have his answer by sundown(probably much sooner)! So, after what seems like an infinity(a couple of hours), the programmer decides to determine how long it would take to run the program to its completion. His check reveals, that the program is verifying an astronomical 15,385 solutions/second. MAN, THAT'S FAST(blazing fast, sizzling fast, unbelievably fast), that's actually more amazing than the astronomical amount of time the slow algoritm, took to run it's course!! The programmer jumps for joy, knowing he'll find the answer, in a relatively short period of time. However, a quick check with a calculator, reveals that, even at more than 15,000 solutions/second, this program, will still take an unbelievable 13,739,888,455 years to complete...

HOW CAN THAT BE? 15,000 SOLUTIONS EVERY SECOND, FOR NEARLY 14 BILLION YEARS!!! THAT MEANS, IF WE WERE ABLE TO HAVE VERIFICATION OF THE EXACT NUMBER OF SOLUTIONS, FOR SUDOKU- THIS BLAZING FAST PROGRAM, WOULD HAVE HAD TO BE INITIATED AT THE DAWN OF TIME!!!!!!

Sudoku Web-Ring Community Forum -Previous-   -Next-   -Join-