Abstract:  

Many languages and models were developed in the AI field to represent and solve problems and issues drawn from the world of discourse. Through the development of the area, it was shown that a vast number of problems can be formulated as CSPs (Constrain Satisfaction Problems), where a solution is bounded to choices that satisfy a predefined set of constraints. The CSPs include a wide range of problems such as the 8-puzzle and the coloring problem. This paper proposes a new algorithm to solve the coloring problem using lists of nonadjacent nodes. Our proposed algorithm consists of two phases as will be shown and achieves better results in terms of backtracking and receiving new variables. The algorithm is analogous to the information propagation schemes that adapt look ahead techniques to detect the dead ends as early as possible. The proposed algorithm overcomes the problem of backtracking, provides no chance for failure to be encountered as long as the problem is solvable.