The 8-Puzzle is a popular single person game that comes in many shapes and sizes. It fundamentally consists of eight squares or tiles that can be moved around a 3X3 board grid. Tiles can be moved one at a time to take up the empty place on the board. The purpose of the game is to create an ordering of letters, numbers or to restore a picture that is printed on the eight tiles of the puzzle. In our game the tiles are numbered 0 to 7.

You will be able to shuffle the tiles and slide them individually to restore the initial numerical ordering.

The followup lesson How do I Tell the Computer to Solve the 8-Puzzle Game? describes the implementation of a commonly used Artificial Intelligence algorithm to solve the 8-Puzzle for you.

We discussed the physical components of the game in the introduction; what we need to focus on now are the computational components that make up the game in LiveCode. Soft components that simulate the physical components are the stack card that serves as the game board, eight square buttons that make up the tiles that slide around the board, and a rectangular button that is used to trigger the shuffle algorithm.

In the background we need to simulate physical constraints that are inherent in the physical design of the game. This is the ability to move tiles and at the same time restrict the order in which tiles can be moved. Tiles can only be moved that are either horizontally or vertically adjacent to the empty space.

The board is created as soon as openStack is called. You should only have to run the following code once, but there is no harm in calling the code several times.

First set up the variables that store information about the game:

# these are local stack variables that store the offset between tiles, the number of tiles
# used horizontally and vertically, the order of the tiles in the winning state and the
# number of the space button
local sOffset, sTilesX, sTilesY, sWinningState, sSpaceButton

Now create openStack that calls a command to initialize the local stack variables and set up the tiles that are to appear on the 3X3 grid.

Note: We are creating nine tiles on the board and then hide the last one. This makes it easier to keep track of the board state and swap tiles around. The Shuffle button is also created in 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
	# make sure the board cannot be resized
	set resizable of me to false
end openStack

Command setGameConstants sets up the local stack variables that store relevant board information. This command takes pPuzzleSizeX and pPuzzleSizeY that specify how many tiles are to appear horizontally and vertically on the game board.

command setGameConstants pPuzzleSizeX pPuzzleSizeY
	local tTile
	# set the offset between the squares on the board
	put 2 into sOffset
	# set up the number of tiles to use
	put pPuzzleSizeX into sTilesX
	put pPuzzleSizeY into sTilesY
	# set up the start up and winning board state
	put empty into sWinningState
	repeat with tTile = 0 to (pPuzzleSizeX * pPuzzleSizeY  - 1)
		if sWinningState is not empty then
			put " " after sWinningState
		end if
		put tTile after sWinningState
	end repeat
	# define what button is used as space
	put pPuzzleSizeX * pPuzzleSizeY - 1 into sSpaceButton
end setGameConstants

Command createBoard places the eight tiles on the stack card. pPadding specifies the amount of space that is to be placed between the top and the left edge of the stack card and the grid of tiles. Command createBoard also populates the button scripts that are executed when you select a tile that is to be moved around the game board.

command createBoard pPadding
	local tHorizontal, tVertical, tButtonNumber
	put 0 into tButtonNumber
	# cycle through the vertical board buttons
	repeat with tVertical = 0 to sTilesY - 1
		# cycle through the horizontal board buttons
		repeat with tHorizontal = 0 to sTilesX - 1
			# create a button that is used as a game tile
			new button "New Button"
			set the width of button "New Button" to 60
			set the height of button "New Button" to 60
			set the location of button "New Button" to \
				pPadding + tHorizontal * (60 + sOffset), pPadding + tVertical * (60 + sOffset)
			# populate the button script for each tile
			set the script of button "New Button" to \
				"on mouseUp" & cr & \
				"local tCurrentState" & cr & \
				"swapButtons " & sSpaceButton & ", " & tButtonNumber & cr & \
				"put boardToBoardState (" & pPadding & \
				") into tCurrentState" & cr & \
				"if manhattanDistance (tCurrentState) is 0 then" & cr & \
				"answer " & quote & "You Made It!" & quote & " with "& quote & \
				"OK" & quote & cr & \
				"end if" & cr & \
				"end mouseUp"
			# give each button a unique name
			set the name of button "New Button" to "b" & tButtonNumber
			add 1 to tButtonNumber
		end repeat
	end repeat
end createBoard

Command writeButtonLabels assigns numbers to the labels of the tiles. The tiles are numbered 0 to 7. 8 is the hidden tile that represents the empty space. Argument pButtonLabelNames is the string of labels that is to be assigned to the tiles.

command writeButtonLabels pButtonLabelNames
	local tButtonLabelName, tButtonNumber
	put 0 into tButtonNumber
	# populate each label of a button with a number
	repeat for each word tButtonLabelName in pButtonLabelNames
		set the label of button ("b" & tButtonNumber) to tButtonLabelName
		add 1 to tButtonNumber
	end repeat
end writeButtonLabels

Command createShuffleButton creates the Shuffle button and populates the script that is called when pressing the button. This command also resizes the card on which the button and tiles are placed.

command createShuffleButton
   # create the shuffle button
   new button
   set the name of the last button to "New Button"
   set label of button "New Button" to "Shuffle"
   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)) + 50
   # populate the button script for the shuffle button
   set the script of button "New Button" to \
         "on mouseUp" & cr & \
         "shuffleBoard 10" & cr & \
         "end mouseUp"
   set the name of button "New Button" to "Shuffle"
   # 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) + 80
end createShuffleButton

The board is now ready, we are just missing the underlying functionality that drives the game.

In order to make the game more challenging, there is a Shuffle button that moves the tiles around. The Shuffle button randomly selects tiles and moves them a set number of times. pTimes specifies how many times a tile is to be moved.

command shuffleBoard pTimes
	local tSwaps, tButtonToSwap, tLastTile
	repeat while tSwaps < pTimes
		# randomly chose a tile
		put random (sSpaceButton) - 1 into tButtonToSwap
		# if the tile is not the last one that was moved and
		# the tile can be moved into the empty space then move
		# it and increment the number of successful moves
		if (tLastTile is not tButtonToSwap) and \
			(isSwapable (sSpaceButton, tButtonToSwap) is true) then
			swapButtons sSpaceButton, tButtonToSwap
			put tButtonToSwap into tLastTile
			add 1 to tSwaps
		end if
	end repeat
end shuffleBoard

One of the most important actions to take is to move tiles around the board. This is easily implemented on a physical board due to the natural constraints that real tiles have. Simulating these constraints in software is somewhat more challenging. The following code implements the physical constraints, but it is easy to change the code to allow for more exotic moves. An example would be to allow tiles to move diagonally.

Function isSwapable provides a test that determines if two tiles are either horizontally or vertically adjacent.

Note: We are using the physical location of the buttons to calculate whether or not a move is possible. pButton1 and pButton2 are the two tiles to be tested.

function isSwapable pButton1, pButton2
	local tRelativeX, tRelativeY
	# calculate the horizontal offset between two button locations
	put item 1 of location of button ("b" & pButton1) - \
		item 1 of location of button ("b" & pButton2) into tRelativeX
	# calculate the vertical offset between two button locations
	put item -1 of location of button ("b" & pButton1) - \
		item -1 of location of button ("b" & pButton2) into tRelativeY
	# if there is only a horizontal or a vertical offset and the offset is of a specific size
	# then the tiles can be swapped
	if (tRelativeX is 0 and abs (tRelativeY) is 60 + sOffset) or \
		(tRelativeY is 0 and abs (tRelativeX) is 60 + sOffset) then
		return true
	else
		return false
	end if
end isSwapable

Command swapButtons swaps two tiles around. A test is also performed to determine whether or not tiles can be swapped. The moves are animated to provide more of a physical game experience. As with isSwapable, buttons pButton1 and pButton2 are the buttons to be swapped.

command swapButtons pButton1, pButton2
	local tRelativeX, tRelativeY, tButtonLocation
	# calculate the horizontal offset between two button locations
	put item 1 of location of button ("b" & pButton1) - \
		item 1 of location of button ("b" & pButton2) into tRelativeX
	# calculate the vertical offset between two button locations
	put item -1 of location of button ("b" & pButton1) - \
		item -1 of location of button ("b" & pButton2) into tRelativeY
	# if there is no horizontal offset but the vertical offset has a specific size
	# then swap the two tiles    
	if (tRelativeX is 0 and abs (tRelativeY) is 60 + sOffset) or \
		(tRelativeY is 0 and abs (tRelativeX) is 60 + sOffset) then
		put location of button ("b" & pButton1) into tButtonLocation
		set the moveSpeed to 65535
		move button ("b" & pButton1) from location of button ("b" & pButton1) to \
			location of button ("b" & pButton2) without messages
		set the moveSpeed to 200
		move button ("b" & pButton2) from location of button ("b" & pButton2) to \
			tButtonLocation without messages
	end if
end swapButtons

Function boardToBoardState produces a string of numbers that specifies the order in which the labels on the tiles appear. pPadding specifies the amount of space that exists between the top and the left edge of the stack card and the grid of tiles.

Note: We have to access the physical button locations in order to determine the order in which the tiles are placed.

function boardToBoardState pPadding
	local tHorizontal, tVertical, tButtonNumber, tPositionArray, tLine, tResult
	# cycle through the vertical board buttons
	repeat with tVertical = 0 to sTilesY - 1
		# cycle through the horizontal board buttons
		repeat with tHorizontal = 0 to sTilesX - 1
			# cycle through the button numbers
			repeat with tButtonNumber = 0 to sTilesX * sTilesY - 1
				# put the number of the button label into an array
				if location of button ("b" & tButtonNumber) is \
					pPadding + tHorizontal * (60 + sOffset), pPadding + tVertical * (60 + sOffset) then
					put tHorizontal + tVertical * sTilesX into tPositionArray [tButtonNumber]
				end if
			end repeat
		end repeat
	end repeat
	# order the array by its keys
	get the keys of tPositionArray
	sort lines of it numeric by tPositionArray[each]
	# convert the list of keys into a string
	repeat for each line tLine in it
		if tResult is not empty then
			put " " after tResult
		end if
		put tLine after tResult
	end repeat
	return tResult
end boardToBoardState

Function manhattanDistance determines by how many squares a tile is displaced from the position that would be considered a winning position. There are simpler ways to determine if a board stated is a winning position, for example comparing pBoardState with the string of the winning board state. We are introducing the manhattan distance her as it will be used in the follow up lessons to help solve the puzzle automatically. pBoardState is a string with a sequence of tiles that is to be tested.

function manhattanDistance pBoardState
	local tButton, tButton1H, tButton1V, tButton2H, tButton2V, tResult
	# test how far each tile is away from its winning location
	# we are not testing the location of the space
	repeat with tButton = 0 to sSpaceButton - 1
		# get the x and y positions of the two buttons to be swapped,
		# with respect to the horizontal and vertical game grid
		put (wordOffset (tButton, sWinningState) - 1) mod sTilesX into tButton1H
		put (wordOffset (tButton, sWinningState) - 1) div sTilesY into tButton1V
		put (wordOffset (tButton, pBoardState) - 1) mod sTilesX into tButton2H
		put (wordOffset (tButton, pBoardState) - 1) div sTilesY into tButton2V
		add abs (tButton1H - tButton2H) + abs (tButton1V - tButton2V) to tResult
	end repeat
	return tResult
end manhattanDistance  

This figure shows you the board you should get when running the code in this lesson. The Shuffle button moves tiles around for you and changes the order in which the tiles are displayed.

To move a single tile, simply click on the tile you would like to move. In this example, you can only move tiles 5 and 7.