A graph-theoretical approach to solving Scramble Squares puzzles

Mason, Sarah; Zhang, Mali

doi:10.2140/involve.2012.5.313

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

A graph-theoretical approach to solving Scramble Squares puzzles

Sarah Mason and Mali Zhang

Vol. 5 (2012), No. 3, 313–325

DOI: 10.2140/involve.2012.5.313

Abstract

A Scramble Squares puzzle is made up of nine square pieces such that each edge of each piece contains half of an image. A solution to the puzzle is obtained when the pieces are arranged in a $3 \times 3$ grid so that the adjacent edges of different pieces together make up a complete image. We describe a graph-theoretical approach to solving Scramble Squares puzzles and a method for decreasing randomness in the backtracking solution algorithm.

Keywords

graph theory, algorithms

Mathematical Subject Classification 2010

Primary: 05C75, 94C15

Milestones

Received: 23 August 2011

Revised: 15 December 2011

Accepted: 15 December 2011

Published: 14 April 2013

Communicated by Arthur T. Benjamin

Authors

Sarah Mason
Department of Mathematics Wake Forest University 127 Manchester Hall Winston-Salem, NC 27109 United States

Mali Zhang
Davidson College Davidson, NC 28035 United States

Vol. 5, No. 3, 2012