The Douglas-Rachford algorithm is an iterative method for finding a point in the intersection of two (or more) closed sets. It is well-known that the iteration (weakly) converges when it is applied to convex subsets of a Hilbert space. Despite the absence of a theoretical justification, the algorithm has also been successfully applied to various non-convex practical problems, including finding solutions for the eight queens problem, or sudoku puzzles. In particular, we will show how these two problems can be easily modelled.

With the aim providing some theoretical explanation of the convergence in the non-convex case, we have established a region of convergence for the prototypical non-convex Douglas-Rachford iteration which finds a point on the intersection of a line and a circle. Previous work was only able to establish local convergence, and was ineffective in that no explicit region of convergence could be given.

PS: Bring your hardest sudoku puzzle :)