We describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbols of each cell updated at each step of the algorithm using estimation of distributions algorithms (EDA). This update is done using the empirical estimators of these probabilities for a fraction of the best puzzles according to a cost function. We develop also some partial restart techniques in the RESEDA algorithm to obtain a convergence for the most diffcult puzzles.