The Sam Loyd 15-Puzzle
Citation:
Hayes, Richard. 'The Sam Loyd 15-Puzzle'. - Dublin, Trinity College Dublin, Department of Computer Science, TCD-CS-2001-24, 2001, pp28Download Item:
Abstract:
This report presents an approach to solve Sam Loyd?s famous 15-puzzle. The 15 or
sliding puzzle is traditionally represented as a 4 * 4 board with tiles numbered from 1
to 15 arranged in numerical order from top left to bottom right of the board. The
object of the puzzle is to rearrange the tiles in this order from any solvable scrambled
starting position. A solvable board is one where the start configuration is an even
permutation of the solved board. This report describes an algorithm that generates
solutions to solvable boards not only for the 15 puzzle, but also for boards of different
dimensions. It adapts a divide and conquer approach outlined in Ian Parberry?s paper
(1997).
Firstly, a brief discussion on the definition and background of the puzzle is offered.
An in-depth explanation of what constitutes a solvable puzzle board is presented - an
analysis of even permutations, which is fundamental to generating a solvable board, is
given. From this, an algorithm to check a permutation for evenness is then illustrated.
The adapted algorithm to solve the 15 or (n2-1) puzzle is then presented along with
the theory and reasoning behind the adaptation, demonstrating different solution cases
depending on where a tile is situated on the puzzle board. Following this, a discussion
on special board configurations that cannot be directly solved by the puzzle algorithm
is offered. A second report will follow on the steps required to generate the worst case
number of moves of a board of a given dimension, which demonstrates that the
adapted algorithm solves the worst case board in substantially less moves than the one
described in [Parberry 1997]. In the appendix of this report appears each series of
moves used in the algorithm to solve a puzzle board.
Author: Hayes, Richard
Publisher:
Trinity College Dublin, Department of Computer ScienceType of material:
Technical ReportCollections
Series/Report no:
Computer Science Technical ReportTCD-CS-2001-24
Availability:
Full text availableKeywords:
Computer ScienceMetadata
Show full item recordLicences: