In this paper, we develop two robust moving horizon state observer (MHSO) algorithms which are capable of handling system non-linear uncertainties and physical state constraints. The algorithms employ open-loop and closed-loop prediction strategies to convert the design into multi-parameter quadratic programming (mp-QP), and also utilize the novel rewinding optimization to eliminate the conflict between open-loop prediction and closed-loop implementation. Based on the optimal solutions to mp-QP problems, MHSO is obtained by a series of offline linear/affline observation polices, and computational complexity is reduced dramatically. The convergence of observation errors, as one of challenges for robust MHSO, is also solved by introducing two auxiliary tuning parameters, the arrival weighting and the arrival observer gain. Finally, a simulation example demonstrates that our algorithms are practical and effective.