Go to  Advanced Search

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

Show full item record

Files in this item

Files Size Format Description   View
ubc_2010_fall_schaad_jason.pdf 2.583Mb Adobe Portable Document Format   View/Open
 
Title: Modeling the 8-queens problem and Sudoku using an algorithm based on projections onto nonconvex sets
Author: Schaad, Jason
Degree Master of Science - MSc
Program Mathematics
Copyright Date: 2010
Publicly Available in cIRcle 2010-09-16
Abstract: 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.
URI: http://hdl.handle.net/2429/28469
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893