Multi-Agent system (MAS) theory has raised more and more attention from researchers and is experiencing a rapid development in recent years. Many methods based on MAS are emerged and proved successful in solving certain problems, and the AER (Agent-environment-rules) model is one of them used in solving constraint satisfaction problems (CSPs). But the statistic strategy for Agents constrains its ability in problem solving. To tackle this problem, simulated annealing (SA) is introduced to provide Agents with more active and effective strategies. Thus, the application of MAS and SA is successfully combined to form an effective model, SAAER (simulated annealing based AER) model, for solving the CSPs. Results from experiments on the classical CSPs, such as N-queen and coloring problems, show that SAAER model can solve the CSPs at a more effective and stable level. For a large-scale N-queen problem, when N=10000, a precise solution can be obtained in about 200 seconds.