IntroductionDetermining SolvabilityOpen Space PositionPuzzle Solution AlgorithmTile MovementsCase 1Case 2Case 3Case 4Corner PlacementSpecial Board ConfigurationIntroductionDetermining SolvabilityPuzzle Solution AlgorithmTile MovementsCorner PlacementSpecial Board . . .Home PageTitle PageJJ IIJ IPage 1 of 16Go BackFull ScreenCloseQuitDemonstration of a Solution Algorithm to the SamLoyd Puzzle of n × nKyle A. BishopDustin L. MadsenDecember 16, 2009AbstractThe paper demonstrates a solution to the Sam Loyd 15-puzzle for any givensize puzzle. It includes discussion and demonstation of things such as solveabilityand methods of moving pieces such as to minimize total moves to solution.IntroductionThe Sam Loyd puzzle was a 4 × 4 grid invented in the 1870’s with numbers 0 through15 on each of the grid spaces, having the number 15 represent the moveable or emptyspace. The puzzle was scrambled up into a beginning start state of the board and aperson was expected to slide the pieces by means of the empty space into a solution,also called the goal state, where the numbers were ordered 0 through 15 from top tobottom. Once the goal state of the board is achieved, the puzzle has been solved. Anexample start state and the goal state for the 4 × 4 puzzle are shown below.IntroductionDetermining SolvabilityPuzzle Solution AlgorithmTile MovementsCorner PlacementSpecial Board . . .Home PageTitle PageJJ IIJ IPage 2 of 16Go BackFull ScreenCloseQuit10712 645 3 158140 112 13 9 10 1 2 345 678 9 10 1112 131415Figure 1: Start State → Goal StateIn order for a puzzle to be solved, it must first be solveable. The first goal ofthis article will be to discuss how solvability is determined for any given puzzle. Ademonstation will be provided that creates a random puzzle of n × n dimensions anddetermines if that puzzle is solveable. This algorithm to determine solveability is dividedinto two parts. First, the algorithm shows solvability when the empty space is alreadyin the goal state position. Second, it provides more information about how to calculatesolvability if the empty space is not in the goal state position.Once it has been shown that a puzzle can actually be solved, the Parberry divideand conquer algorithm[1] can be used to solve the puzzle. The approach used here willbe to use the Parberry algorithm to generate a set of moves which solve a given puzzle.This set of moves will give the ability to generate a step by step solution to the puzzle.Determining SolvabilityWhen determining the solvability of any Sam Loyd puzzle, the first thing that must beconfirmed is whether or not the puzzle has an even or odd amount of permutations to getIntroductionDetermining SolvabilityPuzzle Solution AlgorithmTile MovementsCorner PlacementSpecial Board . . .Home PageTitle PageJJ IIJ IPage 3 of 16Go BackFull ScreenCloseQuitfrom the start state of the puzzle to the goal state. When actually playing the puzzle,each individual piece can only be exchanged with the empty space to achieve movementtowards the goal state. When determining the evenness of the board to check solvability,this restriction is lifted. Each permutation is defined as being the action of picking upany piece from the start state board and putting it into its goal state position. Theoriginal tile that occupied that goal state position is then put into it’s own goal stateposition, and so on. This process begins with the tile in the first position being put intoits goal state position and ends when all numbers are in their goal state position. Everytime one piece is exchanged for another, that is considered one permutation. Whencompleted, the sum of these permutations is then checked as being even or odd. Thisinformation will then be used to help determine solvability.The process of checking to see whether the puzzle has an even or odd amount ofpermutations begins with first arranging the given puzzle into a list rather than matrixform. This makes exchanges easier to work with. The goal state is also put into thisform and placed underneath the start state as a reference for movements. Each time apermutation is performed, that number which was moved will be recorded into a list forpurposes of counting the amount of permutations later. A simple start state is given inthis form for a 4 × 4 puzzle:IntroductionDetermining SolvabilityPuzzle Solution AlgorithmTile MovementsCorner PlacementSpecial Board . . .Home PageTitle PageJJ IIJ IPage 4 of 16Go BackFull ScreenCloseQuit1 2 0 345 678 9 10 1112 13 1514Figure 2StartState : [1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14]GoalState : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]The starting move would be to take the first positioned piece, in this case the 1, fromthe start state into its goal state position which is currently occupied by the 2. An Xwill represent the empty spot on the board from picking up the first piece in each cycleand it is assumed that the next piece being placed into its goal state position is held inhand.StartState : [X, 1, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14]GoalState : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]Interchanges : [1]In − Hand : (2)IntroductionDetermining SolvabilityPuzzle Solution AlgorithmTile MovementsCorner PlacementSpecial Board . . .Home PageTitle PageJJ IIJ IPage 5 of 16Go BackFull ScreenCloseQuitNext, the 2 in hand will be placed into it’s goal state position, currently held by the0.StartState : [X, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14]GoalState : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]Interchanges : [1, 2]In − Hand : (0)The 0 is then placed into its goal state position which is currently occupied by nonumber, thus ending the interchanges for now. This is considered one permutation cycleand it’s total amount of interchanges, two, will be added to those of any more cycleswhich may or may not be needed to be performed in order to achieve the goal state.StartState : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14]GoalState : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]Interchanges : [1, 2, 0]In − Hand : (−)Continuing the process, the next number to be put into it’s goal state would be the15. Note, that since every piece in between where our first interchange took place isalready in its goal state position, they do not need to be interchanged Since one cyclewas completed, we will start a new cycle and record the interchanges.StartState : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,