Open Collections

Modeling the 8-queens problem and Sudoku using an algorithm based on projections onto nonconvex sets

University of British Columbia

We begin with some basic definitions and concepts from convex analysis and projection onto convex sets (POCS). We next introduce various algorithms for converging to the intersection of convex sets and review various results (Elser’s Difference Map is equivalent to the Douglas-Rachford and Fienup’s Hybrid Input-Output algorithms which are both equivalent to the Hybrid Projection-Reflection algorithm). Our main contribution is two-fold. First, we show how to model the 8-queens problem and following Elser, we model Sudoku as well. In both cases we use several very nonconvex sets and while the theory for convex sets does not apply, so far the algorithm finds a solution. Second, we show that the operator governing the Douglas-Rachford iteration need not be a proximal map even when the two involved resolvents are; this refines an observation of Eckstein.

Text

2010-09-16

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/28469

Mathematics

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/