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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

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