Abstract: Non-binary constraint satisfaction problems (NB-CSPs) are transformed into the integer constrained minimization problems by extending correlative definitions of E-GENET. Then, a class of discrete Lagrangian-based search scheme and algorithm with non-binary variable constraints (NB-LSDL) is proposed for such problems to restructure E-GENET from NB-LSDL. It is useful to gain important insights into the heuristic repair method to minimize conflicts and improve variant of E-GENET for the CSPs with general constraints in a new theoretical perspective. The experimental results show that it is effective and feasible to re-extend E-GENET by using NB-LSDL.