# How do I Tell the Computer to Solve the 8-Puzzle Game?

This lesson describes how to make the computer solve the 8-Puzzle for you, using a commonly applied Artificial Intelligence search technique. A top level discussions of the key algorithm is given, and code samples are provided.

## Introduction

This is an extension of lesson How do I Create an 8-Puzzle Game? and implements an Iterative Deepening Depth-First Search algorithm to solve the 8-Puzzle. Lesson How do I Create an 8-Puzzle Game? is an essential prerequisite for the information covered here.

Iterative Deepening Depth-First Search is a well established Artificial Intelligence technique that is used to explore a search space in a relatively memory efficient way in order to find the shortest possible path, or in this case the least number of moves required to solve the 8-Puzzle. The key disadvantage of Iterative Deepening Depth-First Search is the nature by which it finds its solution. The time complexity is exponential, which means that the algorithm can become rather slow when having to solve long paths. In this particular example, the time to find a solution increases by a factor of approximately 2.7 for each additional move that is needed to solve the puzzle.

Let us put this information into perspective and assume we have three board states that have to be solved. Board state A can be solved in one move, board state B can be solved in 5 moves and board state C can be solved in 10 moves. In order to find the moves to these games, Iterative Deepening Depth-First Search has to explore approximately the following number of states for each game: A: 2.7 states, B: 143.5 states and C: 20589 states.

A whole range of other algorithms exist that are computationally faster for long paths, but these do not necessarily guarantee the shortest possible number of moves. Look at Heuristic Search if you are interested in alternative ways of solving the 8-Puzzle. An implementation of A* (A Star) is available in lesson How do I Tell the Computer to Solve the 8-Puzzle Game Using A*?.

## Integrating the Functionality

Please update the *openStack* code from lesson How do I Create an 8-Puzzle Game? with the following *openStack* code. This adds a Solve button to the board and populates that button with the LiveCode script to run the Iterative Deepening Depth-First Search algorithm.

**Note:** Only one comment and one line of code have been added to the original *openStack*.

**on** openStack**
# set up the constants for the game type**
setGameConstants 3, 3**
# remove any previous buttons that may already be on the card
# this prevents us from duplicating existing buttons**
repeat while the number of buttons of this card > 0**
delete** button 1 of this card**
end** **repeat**
# create the board buttons
createBoard 50**
# write the values onto the buttons**
writeButtonLabels sWinningState**
# create the space on the board**
hide button ("b" & sSpaceButton)**
# create the shuffle button**
createShuffleButton**
# create the solve button**
createSolveButton**
# make sure the board cannot be resized**
set resizable of me to false**
end** openStack

## The Solve Button

Command *createSolveButton* creates the Solve button and populates the script that is called when pressing the button. This command also resizes the card on which the game buttons and tiles are placed.

**command** createSolveButton
**# create the shuffle button**
**new** button
**set** the name of the last button to "New Button"
**set** label of button "New Button" to "Solve"
**set** width of button "New Button" to 60 * sTilesX + sOffset * (sTilesX - 1)
**set** location of button "New Button" to (60 * sTilesX + sOffset * (sTilesX - 1)) / 2 + 20, \
(60 * sTilesY + sOffset * (sTilesY - 1)) + 96
**# populate the button script for the shuffle button**
**set** the script of button "New Button" to \
"on mouseUp" & cr & \
"solvePuzzle 50" & cr & \
"end mouseUp"
**set** the name of button "New Button" to "Solve"
**# resize the board for the buttons**
**set** the width of me to 60 * sTilesX + sOffset * (sTilesX - 1) + 40
**set** the height of me to 60 * sTilesY + sOffset * (sTilesY - 1) + 126**
end** createSolveButton

## Managing the Solution Process

Command *solvePuzzle* performs all steps needed to solve the 8-Puzzle. This includes testing whether or not the first board state is already the winning board state, calling Iterative Deepening Depth-First Search and moving the tiles back into the positions that are defined to be the solution state. *pPadding* specifies the amount of space that exists between the top and the left edge of the stack card and the grid of tiles.

**command** solvePuzzle pPadding**
local** tCurrentState, tPossibleMove, tMove, tDepth, tSolution**
# get the current board state that needs to be solved**
put boardToBoardState (pPadding) into tCurrentState**
# iteratively deepen the search to find the shortest solution for the board state**
if manhattanDistance (tCurrentState) is 0 **then**
answer "Puzzle is Already Solved!" with "OK"**
else
repeat** while tSolution is empty**
put** tDepth + 1 into tDepth**
# update the solve button with search information**
set label of button "Solve" to "Tree Depth: " & tDepth**
# wait to ensure the label is updated**
wait for 10 milliseconds**
repeat** with tPossibleMove = 0 to (sTilesX * sTilesY - 1)**
put** IDDFS (deriveNextState (tCurrentState, tPossibleMove, "8"), \
tPossibleMove, tDepth) into tSolution**
if** tSolution is not empty **then
exit** **repeat
end** **if
end** **repeat
end** **repeat**
# set the button label back to solve
set label of button "Solve" to "Solve"**
# solve the board with the steps returned from the state space search algorithm**
repeat for each word tMove in tSolution
swapButtons 8, tMove, 2**
end** **repeat**
answer "I Made It!" with "OK"**
end** **if
end** solvePuzzle

## The Iterative Deepening Depth-First Search Algorithm

Function *IDDFS* is a short function that calls itself recursively in order to explore the search space. Within this function the logic performs three key tasks.

1. If we have found the winning state, then return the last tile that got us to this winning state.

2. If we have not found the winning state, call *IDDFS* again with a possible new move to explore.

3. If we are coming out of the recursion on the solution path then add the last tile that was moved to the list of moves that solve the puzzle.

The arguments passed to *IDDFS* are changed at each recursive call. *pCurrentState* specifies the current board state that is evaluated on this branch of the function call. *pMove* specifies the last move that was necessary to reach the current tile configuration that is defined by *pCurrentState*. *pDepth* is the current branch depth that must not be exceeded. This is used to control the iterative depth of the search.

**function** IDDFS pCurrentState, pMove, pDepth**
local** tPossibleMove, tSolution, tResult**
put** empty into tResult**
if** pCurrentState is not empty and pDepth is not 0 **then
if** manhattanDistance (pCurrentState) is 0 **then**
# if pCurrentState is the winning state
# then return the number of the tile that had to be moved to get here
put pMove into tResult**
else
repeat** with tPossibleMove = 0 to (sTilesX * sTilesY - 1)**
# call IDDFS recursively with a new potential branch to explore **
put IDDFS (deriveNextState (pCurrentState, tPossibleMove, "8"), \
tPossibleMove, pDepth - 1) into tSolution**
if** tSolution is not empty **then**
# if we are coming back out of the search tree and we are
# on the solution path then add the tile that was used to get
# us to this state to the moves on the solution path
put pMove & " " & tSolution into tResult**
exit** **repeat
end** **if
end** **repeat
end** **if
end** **if**
return tResult**
end** IDDFS

## Deriving the Next Step

In order to explore a search space, *IDDFS* must know what the next branches of a particular tree node are. Function *deriveNextState* provides this information for a particular set of arguments.

*pCurrentState* is a node state for which a branch is to be found. *pSwap1* and *pSwap2* are tiles that should be swapped around in the resulting board state. If *pSwap1* and *pSwap2* cannot be swapped, then the result is empty.

**function** deriveNextState pCurrentState, pSwap1, pSwap2**
local** tHorizontal, tVertical, tButton1Horizontal, tButton2Horizontal, \
tButton1Vertical, tButton2Vertical, tResult**
# get the x and y positions of the two buttons to be swapped,
# with respect to the horizontal and vertical game grid**
put (wordOffset (pSwap1, pCurrentState) - 1) mod sTilesX into tButton1Horizontal**
put** (wordOffset (pSwap1, pCurrentState) - 1) div sTilesY into tButton1Vertical**
put** (wordOffset (pSwap2, pCurrentState) - 1) mod sTilesX into tButton2Horizontal**
put** (wordOffset (pSwap2, pCurrentState) - 1) div sTilesY into tButton2Vertical**
# determine if the two buttons can be swapped
# if so create a new state that represents the swap**
if ((tButton1Horizontal - tButton2Horizontal is 0) and \
(abs (tButton1Vertical - tButton2Vertical) is 1)) or \
((tButton1Vertical - tButton2Vertical is 0) and \
(abs (tButton1Horizontal - tButton2Horizontal) is 1)) **then**
put pCurrentState into tResult**
replace** pSwap1 with "X" in tResult**
replace** pSwap2 with pSwap1 in tResult**
replace** "X" with pSwap2 in tResult**
else**
put empty into tResult**
end** **if**
return tResult**
end** deriveNextState

## The 8-Puzzle Board (Finding the Solution)

The button at the bottom of the game board states "Solve" in interactive playing mode. Once this button is selected, the text changes to "Tree Depth: X", indicating the depth at which the nodes are being explored. The tree depth "X" increments until a solution is found.

For

# wait to ensure the label is updated

wait for 10 milliseconds

to be effective, you must add "with messages":

wait for 10 millisecs with messages

and it would be wise to add "with messages" to the repeat statement as well:

repeat while tSolution is empty with messages.

You should do this with all repeat loops.

If I understand it correctly, this is a brute force solution and not really AI (although in the end you might always ask what is AI). Human beings tend to search for a smart solution rather than checking every single possibility.

Other than that, this is a really interesting algorithm for solving small jigsaw puzzles. Thank you for this nice example!