A new, to our knowledge, algorithm for the phase unwrapping (PU) problem that is based on stochastic relaxation is proposed and analyzed. Unlike regularization schemes previously proposed to handle this problem, our approach dispells the following two assumptions about the solution: a Gaussian model for noise and the magnitude of the true phase-field gradient's being less than pi everywhere. We formulate PU as a constrained optimization problem for the field of integer multiples of 2pi, which must be added to the wrapped phase gradient to recover the true phase gradient. By solving the optimization problem using simulated annealing with constraints, one can obtain a consistent solution under difficult conditions resulting from noise and undersampling. Results from synthetic test images are reported.