Prior knowledge of lesson How do I Create an 8-Puzzle Game?  is essential and an understanding of lesson How to I Tell the Computer to Solve the 8-Puzzle Game? would be an advantage. The brute force algorithm discussed in How to I Tell the Computer to Solve the 8-Puzzle Game? is not relevant to this lesson but should provide you with an alternative view on how to solve puzzles like the 8-Puzzle.

A* (A Star) is a state space search algorithm that makes informed judgements about the cost involved in solving the puzzle. Two fundamental values feed into assessing the cost of a particular move on the board:

g: is the number of tiles that have moved to reach a board state that is being assessed

h: is the estimated cost to solve the board state that is currently being assessed

g can be calculated accurately by counting the number of moves we have already taken.

h is calculated using a heuristic that provides an underestimating cost to solve the game. The heuristic we use here is called the manhattan distance and calculates by how many squares a tile is displaced from the location that the tile would have to be in to form part of the winning board state.

This gives us the following cost assessment for any state in the search space: f = g + h

Using a heuristic to solve the 8-Puzzle, rather than brute force, as described in How to I Tell the Computer to Solve the 8-Puzzle Game? allows us to find a solution to the puzzle in less time. You can test the algorithms side by side to see the performance difference.

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 A* 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

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

Command solvePuzzle performs all the steps need to solve the 8-Puzzle. This includes testing whether or not the first board state is already the winning board state, calling the cost function costGH and exploreStates to explore the next potential paths that may lead to a solution. pPadding specifies the amount of space that exists between the top and the left edge of the stack cards and the grid tiles.

command solvePuzzle pPadding
	local tStatesToExplore, tExploredStates, tMove
	# create the first state to explore and calculate its estimated cost
	put "," & boardToBoardState (pPadding) into tStatesToExplore
	if manhattanDistance (item 2 of tStatesToExplore) is 0 then
		answer "Puzzle is Already Solved!" with "OK"
	else
		put costGH (tStatesToExplore) & "," & tStatesToExplore into tStatesToExplore
		repeat until tStatesToExplore is empty
			if manhattanDistance (item 3 of line 1 of tStatesToExplore) is 0 then
				repeat for each word tMove in item 2 of line 1 tStatesToExplore
					swapButtons sSpaceButton, tMove
				end repeat
				answer "I Made It!" with "OK"
				exit repeat
			else
				exploreStates tStatesToExplore, tExploredStates
			end if
		end repeat
	end if
end solvePuzzle

Command exploreStates takes pointers to two lists of states that are to be explored and that have already been explored. This information is important as it allows the search algorithm to make an informed decision as to whether a new state is better or worse than states that have been visited in the past or states that are to be visited in the future.

command exploreStates @pStatesToExplore, @pExploredStates
	local tNewStates, tResult
	# get the next possible moves for pStateToExplore 
	put getNewStatePaths (line 1 of pStatesToExplore) into tNewStates
	# move the state path that is being explored to pExploredStates
	if pExploredStates is not empty then
		put cr after pExploredStates
	end if
	put line 1 of pStatesToExplore after pExploredStates
	# remove the state path that is being explored from pStatesToExplore
	put line 2 to -1 of pStatesToExplore into pStatesToExplore 
	# prune the existing explored and unexplored search space
	pruneStateSpace tNewStates, pStatesToExplore, pExploredStates
	# sort pStatesToExplore so the cheapest path is located at the beginning
	sort lines of pStatesToExplore numeric by item 1 of each   
end exploreStates

Function getNewStatePaths produces a list of possible states that can be reached by moving one tile from the most recent state of pPath. pPath is the only parameter passed to this function. All possible next steps are returned by tResult.

function getNewStatePaths pPath
	local tPossibleMove, tNewPath, tResult
	# we are testing for all possible tile moves 
	# from the most recent state of the current path 
	repeat with tPossibleMove = 0 to sSpaceButton - 1
		put deriveNextState (pPath, tPossibleMove, sSpaceButton) into tNewPath
		if tNewPath is not empty then
			if tResult is not empty then
				put cr after tResult
			end if
			put tNewPath after tResult
		end if
	end repeat
	return tResult
end getNewStatePaths

Function deriveNextState takes three arguments and tries to add a new state to the path that is passed in by the argument pCurrentPath. pSwap1 and pSwap2 are the tiles that are to be swapped in order to create the new state. If tiles pSwap1 and pSwap2 cannot be swapped, then deriveNextState returns empty.

pCurrentPath and the non empty tResult are comma delimited strings with item 1 containing the current cost f of the path, item 2 containing the individual moves that can later be replayed when solving the 8-Puzzle and items 3 to n containing the individual board states that make up the path that is being explored.

function deriveNextState pCurrentPath, pSwap1, pSwap2
	local tHorizontal, tVertical, tButton1H, tButton2H, \
		tButton1V, tButton2V, tPossibleNewState, tResult
	# get the x and y positions of the two buttons to be swapped
	# with respect to the horizontal and vertical game grid of the first
	# state of the current path
	# we are using item 3 here as item 1 is the cost of the path and
	# item 2 contains the moves needed to solve the puzzle
	put (wordOffset (pSwap1, item 3 of pCurrentPath) - 1) mod sTilesX into tButton1H
	put (wordOffset (pSwap1, item 3 of pCurrentPath) - 1) div sTilesY into tButton1V
	put (wordOffset (pSwap2, item 3 of pCurrentPath) - 1) mod sTilesX into tButton2H
	put (wordOffset (pSwap2, item 3 of pCurrentPath) - 1) div sTilesY into tButton2V
	# determine if the two buttons can be swapped,
	# if so create a new state that represents the swap
	if ((tButton1H - tButton2H is 0) and (abs (tButton1V - tButton2V) is 1)) or \
		((tButton1V - tButton2V is 0) and (abs (tButton1H - tButton2H) is 1)) then
		put item 3 pCurrentPath into tPossibleNewState
		replace pSwap1 with "X" in tPossibleNewState
		replace pSwap2 with pSwap1 in tPossibleNewState
		replace "X" with pSwap2 in tPossibleNewState
		# check here if we have a loop in the path and reject it if so
		if itemOffset (tPossibleNewState, item 3 to -1 of pCurrentPath) is 0 then
			# add the new state to the front of other states
			put tPossibleNewState & "," & item 3 to -1 of pCurrentPath into tResult
			# add the move that got us to this new state to the list of moves we made so far
			if item 2 of pCurrentPath is empty then
				put pSwap1 & "," & tResult into tResult
			else
				put item 2 of pCurrentPath && pSwap1 & "," & tResult into tResult
			end if
			put costGH (tResult) & "," & tResult into tResult
		end if
	end if
	return tResult
end deriveNextState

Function costGH calculates the cost f for a given path pPath.

function costGH pPath
	local tMove, tResult
	# calculate g for pPath
	repeat for each word tMove in item 1 of pPath
		add 1 to tResult
	end repeat
	# calculate h for pPath and add it to g
	add manhattanDistance (item 2 of pPath) to tResult
	return tResult
end costGH 

Command pruneStateSpace take a set of paths that are to be explored and tries to add them to pStatesToExplore. A successful add depends on whether or not a potentially better path already exists in pStatesToExplore or pExploredStates.

Note: pStatesToExplore and pExploredStates are passed in by reference. This means that any changes made to their content will be permanent and affects their use outside the scope of this command.

command pruneStateSpace pNewPaths, @pStatesToExplore, @pExploredStates
	local tPath, tStatesToExploreDuplicate, tExploredStatesDuplicate, tAddFlag
	repeat for each line tPath in pNewPaths
		put false into tAddFlag
		# find out if the new state to explore exists 
		# as a head in one of the already explored states
		put stateMatch (tPath, pExploredStates) into tExploredStatesDuplicate
		# find out if the new state to explore exists
		# as a head in one of the states that are still to be explored
		put stateMatch (tPath, pStatesToExplore) into tStatesToExploreDuplicate
		if tExploredStatesDuplicate is false and tStatesToExploreDuplicate is false then
			# if we found no match, then set a flag to add the new path
			# to the paths that are to be explored
			put true into tAddFlag
		else if tExploredStatesDuplicate is not false and item 1 of tPath < \
 			item 1 of line tExploredStatesDuplicate of pExploredStates then 
			# if we found a match with the states we already explored and the new path
			# is cheaper then remove the matched state from the explored states
			# and set the flag to add the new path to the paths that are to be explored
			delete line tExploredStatesDuplicate of pExploredStates
			put true into tAddFlag
		else if tStatesToExploreDuplicate is not false and item 1 of tPath < \
			item 1 of line tStatesToExploreDuplicate of pStatesToExplore then 
			# if we found a match with the states we have not yet explored and the new
			# path is cheaper then remove the matched state from the unexplored states
			# and set the flag to add the new path to the paths that are to be explored
			delete line tStatesToExploreDuplicate of pStatesToExplore 
			put true into tAddFlag
		end if
		# if tAddFlag is set then add the new path to the paths that are to be explored
		# any new paths that exist for which tAddFlag is not set to true are skipped
		if tAddFlag is true then
			if pStatesToExplore is not empty then
				put cr after pStatesToExplore
			end if
			put tPath after pStatesToExplore
		end if
	end repeat
end pruneStateSpace

Function stateMatch tests whether or not the most recent state in a new path matches one of the most recent states in a list of paths. This function returns false if no match was found or the location where the path match was found.

function stateMatch pPath, pPathList
	local tPath, tLineCount
	repeat for each line tPath in pPathList
		add 1 to tLineCount
		if item 3 of tPath is item 3 of pPath then
			return tLineCount
		end if
	end repeat
	return false
end stateMatch

The puzzle interface from this lesson works in the same way as the puzzle interface from lesson How do I Tell the Computer to Solve the 8-Puzzle?. The only difference is that the label on the Solve button does not change. This is because the search algorithm is iterative, rather than recursive and we are not exploring the search space in a depth first fashion.