Robert Tovey, Jingwei Liang, The fun is finite: Douglas-Rachford and Sudoku puzzle – Finite termination and local linear convergence – Journal of Applied and Numerical Optimization

Robert Tovey, Jingwei Liang, The fun is finite: Douglas-Rachford and Sudoku puzzle – Finite termination and local linear convergence

Full Text: PDF
DOI: 10.23952/jano.3.2021.3.01
Volume 3, Issue 3, 31 December 2021, Pages 435-456

Abstract. In recent years, the Douglas-Rachford splitting method has been shown to be effective at solving many non-convex optimization problems. In this paper, a local convergence analysis for non-convex feasibility problems is presented and both finite termination and local linear convergence are obtained. For a generalization of the Sudoku puzzle, it is proved that the local linear rate of convergence of Douglas-Rachford is exactly $\frac{\sqrt{5}}{5}$ and independent of puzzle size. For the s-queens problem, it is proved that Douglas-Rachford converges after a finite number of iterations. Numerical results on solving Sudoku puzzles and s-queens puzzles are provided to support our theoretical findings.

How to Cite this Article:
Robert Tovey, Jingwei Liang, The fun is finite: Douglas-Rachford and Sudoku puzzle – Finite termination and local linear convergence, J. Appl. Numer. Optim. 3 (2021), 435-456.