Abstract: Constraint satisfaction problem (CSP) is an important research topic in the field of artificial intelligence,and arc consistency (AC) is an effective technology to improve the CSP solving efficiency.The symbolic algebraic decision diagram (ADD) algorithm for arc consistency was proposed here to improve the traditional arc consistency technology and was applied in CSP solving.In this paper,ADD was used to compress the search space.It can process multiple constrains in one time,not as the traditional algorithm which can only deal with one value pair in a constraint per step.Fistly,CSP was described as pseudo-Boolean function by 01coding and represented by ADD.Secondly,based on traditional arc consistency algorithm,the ADD operations intersection,union and abstraction were used to achieve constraint propagation and variable domain filtering.Finally,the symbolic algebraic decision diagram (ADD) algorithm for arc consistency was embedded in BT search algorithm to solve the CSP.The result of experimental simulation to solve some problems in benchmark and randomly generated test case shows that the efficiency is higher than backjumping algorithm maintained with AC,such as MAC3+BJ and MAC2001+BJ,meanwhile the performance is better than algorithms BT+MPAC and BT+MPAC* which is based on AC preprocess realized by traditional data structure in CSP solving.

Key words: Constraint satisfaction problem(CSP),Algebraic decision diagram(ADD),Arc consistency(AC)