4 ms·
Enumerating all solutions and checking will always be the simplest approach for find the set of inputs returning true for a decision problem. However, a constra
by anewhnaccount2 7y ago
Enumerating all solutions and checking will always be the simplest approach for find the set of inputs returning true for a decision problem. However, a constraint solver will not necessarily have to enumerate all solutions.
- todd8 7y agoYes it would take a long time to do it that way since there would be roughly 25 billion solutions to evaluate. My Python program doesn’t do this and runs very fast. Elapsed time for this program is approximately 0.03 seconds on my 2013 desktop and it finds all possible solution (in this case one). Normally, inner loops are executed more times than outer loops, but in this program the bodies of the inner loops are skipped (because of the continue statements) when constraints fail in the the outer loops. The five loop bodies are executed a total of 120, 2880, 1440, 1440, 960 times respectively (I put counters in each loop to determine this, all counters were initialized before any of the loops begin). I wrote this program (for a different version of this same problem) while waiting for my daughter to come downstairs to be driven to school one morning around five years ago. (See https://news.ycombinator.com/item?id=7734998 https://news.ycombinator.com/item?id=7734998)