Ant Colony Optimization (ACO) is an efficient way to solve binary constraint-satisfaction problems (CSPs). In recent years, new improvements have only considered enhancing the positive feedback to increase the convergence speed. However, through the study and analysis of these enhanced ACO algorithms, we determined that they still suffer from the problem of easily getting in locally optimal solutions. Thus, an improved ACO algorithm with a strengthened negative-feedback mechanism is designed to tackle CSPs. This new algorithm takes advantage of search-history information and continually obtains failure experience to guide the ant swarm exploring the unknown space during the optimization process. The starting point of this algorithm is to utilize the negative feedback to improve the diversity of solutions. Finally, we use 24 CSP samples and 25 Queen samples to perform experiments, compare this algorithm with other related algorithms and conduct performance assessment. The preliminary results show that ACO with negative feedback outperforms the compared algorithms in identifying high-quality solutions.