Constraint programming is definitly the technology of choice for solving Sudoku puzzles. There is a nice article by Helmut Simonis (http://www.4c.ucc.ie/~hsimon

Constraint programming is definitly the technology of choice for solving Sudoku puzzles. There is a nice article by Helmut Simonis (http://www.4c.ucc.ie/~hsimonis/shikaku.pdf http://www.4c.ucc.ie/~hsimonis/shikaku.pdf) that shows how good various propagation strengths and model variants are for solving 9 times 9 Sudokus (short answer, full propagation on individual rows/columns/squares plus shaving never needs search). For 25 times 25 Sudokus on the other hand, propagation alone is in my experience not enough, and a lot of search is needed.