{"title":"Optimal Solution of Constraint Satisfaction Problems","authors":"Jeffrey L. Duffany","country":null,"institution":"","volume":25,"journal":"International Journal of Computer and Information Engineering","pagesStart":216,"pagesEnd":220,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/2428","abstract":"An optimal solution for a large number of constraint\nsatisfaction problems can be found using the technique of\nsubstitution and elimination of variables analogous to the technique\nthat is used to solve systems of equations. A decision function\nf(A)=max(A2) is used to determine which variables to eliminate. The\nalgorithm can be expressed in six lines and is remarkable in both its\nsimplicity and its ability to find an optimal solution. However it is\ninefficient in that it needs to square the updated A matrix after each\nvariable elimination. To overcome this inefficiency the algorithm is\nanalyzed and it is shown that the A matrix only needs to be squared\nonce at the first step of the algorithm and then incrementally updated\nfor subsequent steps, resulting in significant improvement and an\nalgorithm complexity of O(n3).","references":null,"publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 25, 2009"}