# Solving Eight Puzzle with A* Algorithm in Swift

## A great graph algorithm in Swift

Hallo vrienden, Leo hier.

Today we'll talk about a very great graph search algorithm called A* ( A Star). This algorithm main objective is to find path in the graph based on some conditions that you can choose ( also know as Heuristic).

We will not run into the deep dive of the A Star algorithm time complexity because depends on the implementation, but we can sure say that one of the greatest drawbacks of the A Star is the space complexity. The A Star depends on saving all the previous paths to compare each one heuristics to decide what's the next best step towards a target.

Interested in solving the Eight Puzzle with a neat algorithm? Stay with me in this interesting post.

Let's code! But first....

## The Painting

The today painting is the **Constellation: The Morning Star**, a 1940 piece of art from Joan Miro. Since the post it's about A Star, I found the morning star very suitable to introduce this painter work in this blog.

Joan Miró I Ferrà, born 20 April 1893 and death 25 December 1983, was a Spanish painter, sculptor, and ceramicist born in Barcelona.

Earning international acclaim, his work has been interpreted as Surrealism, a sandbox for the subconscious mind, a re-creation of the childlike, and a manifestation of Catalan pride. In numerous interviews dating from the 1930s onwards, Miró expressed contempt for conventional painting methods as a way of supporting bourgeois society, and famously declared an "**assassination of painting**" in favour of upsetting the visual elements of established painting.

## The problem

You have an Eight Puzzle to solve.

We all have been in this place before, went to a party or a city fair and won some little puzzle that has one piece missing and all other pieces forms a image. Like this image below:

Or this:

Now imagine that all the tiles of the puzzle above are numbers like:

```
let endState = [["1","2","3"],
["4","5","6"],
["7","8","0"]]
```

Where zero means the empty tile. Suddenly we can use graph search algorithm to solve our problems!

## The algorithm

The idea of the algorithm is not very simple but it's easier when you use images know what is going on. Imagine the first state would be this:

**1 Step** - of the algorithm is to generate all the possible next moves for this position aggregating with the previous step, in this case are two possible board states.

This position:

And this position:

Now the algorithm has two paths. The first position and the second position to choose. Like the image above...

But how it decides where to go? For the **Second Step** we'll be using heuristic of course! Heuristic is a 10 dollar word for a 5 cents meaning. The heuristic is just some arbitrary decision that an algorithm has to make to improve it's speed/space/etc.

The heuristic chosen was: How many tiles are placed correctly? . So the algorithm will always prioritize the path with less misplaced tiles. If you want to optimize space, you could do the algorithm choose the first one and discard all the others. If you want to prioritize the best solution, it should always keep track of all possibilities and it's where the A* weakness lives.

The **third step** is just a check if the algorithm selected the actual solution for the problem and it's done! If not, go back to step one and try new board configurations until find the right one.

This would be the final state.

## The Algorithm

The code above you can import directly to you Xcode Playground and run it to test.

```
import Foundation
enum Direction { // mark 1
case up, down, left, right
}
struct AStarPuzzle { // mark 2
var heuristics: Int
var boardPathStateList: [[[String]]]
}
class PuzzleSolver { // mark 3
var state: [[String]] = []
let endState = [["1","2","3"], // mark 4
["4","5","6"],
["7","8","0"]]
func availableMoves(state: [[String]]) -> [[[String]]] { // mark 5
var possibleBoardStates: [[[String]]] = []
let tmpState = state
if let i = tmpState.firstIndex(where: { $0.contains("0") }),
let j = tmpState[i].firstIndex(of: "0") {
if i < 2 {
possibleBoardStates += (movePieceInDirection(.down, board: state, piece: (i, j)))
}
if i > 0 {
possibleBoardStates += (movePieceInDirection(.up, board: state, piece: (i, j)))
}
if j < 2 {
possibleBoardStates += (movePieceInDirection(.right, board: state, piece: (i, j)))
}
if j > 0 {
possibleBoardStates += (movePieceInDirection(.left, board: state, piece: (i, j)))
}
}
return possibleBoardStates
}
func movePieceInDirection(_ direction: Direction, board: [[String]], piece: (Int, Int)) -> [[[String]]] { // mark 6
var movements: [[[String]]] = []
switch direction {
case .up:
var boardCopy = board
let tmp = boardCopy[piece.0][piece.1]
boardCopy[piece.0][piece.1] = boardCopy[piece.0 - 1][piece.1]
boardCopy[piece.0 - 1][piece.1] = tmp
movements.append(boardCopy)
case .down:
var boardCopy = board
let tmp = boardCopy[piece.0][piece.1]
boardCopy[piece.0][piece.1] = boardCopy[piece.0 + 1][piece.1]
boardCopy[piece.0 + 1][piece.1] = tmp
movements.append(boardCopy)
case .left:
var boardCopy = board
let tmp = boardCopy[piece.0][piece.1]
boardCopy[piece.0][piece.1] = boardCopy[piece.0][piece.1 - 1]
boardCopy[piece.0][piece.1 - 1] = tmp
movements.append(boardCopy)
case .right:
var boardCopy = board
let tmp = boardCopy[piece.0][piece.1]
boardCopy[piece.0][piece.1] = boardCopy[piece.0][piece.1 + 1]
boardCopy[piece.0][piece.1 + 1] = tmp
movements.append(boardCopy)
}
return movements
}
func misplacedPiecesHeuristic(state: [[String]]) -> Int { // mark 7
var misplaced = 0
var comparator = 1
for line in state {
for number in line {
if number != "\(comparator)" {
misplaced += 1
}
comparator += 1
}
}
return misplaced
}
func aStarSearch(start: [[String]]) -> AStarPuzzle { // mark 8
var explored = [[[String]]]() // mark 9
var pathList = [AStarPuzzle(heuristics: misplacedPiecesHeuristic(state: start), boardPathStateList: [start])] // mark 10
var path: AStarPuzzle = AStarPuzzle(heuristics: 1, boardPathStateList: [])
while true { // mark 11
let currentBestHeuristicIndex = pathList.indices.reduce(0, { pathList[$1].heuristics < pathList[$0].heuristics ? $1 : $0 }) // mark 12
path = pathList.remove(at: currentBestHeuristicIndex) // mark 13
//pathList.removeAll() to greedy solve with more steps but much less space
let finalStateBoardFromBestHeuristic = path.boardPathStateList.last!
if explored.contains(finalStateBoardFromBestHeuristic) { continue } // mark 14
for movement in availableMoves(state: finalStateBoardFromBestHeuristic) { // mark 15
if explored.contains(movement) { continue }
let heuristic = path.heuristics + misplacedPiecesHeuristic(state: movement) + misplacedPiecesHeuristic(state: finalStateBoardFromBestHeuristic) // mark 16
let new = path.boardPathStateList + [movement]
pathList.append(AStarPuzzle(heuristics: heuristic, boardPathStateList: new))// mark 17
}
explored.append(finalStateBoardFromBestHeuristic)
if finalStateBoardFromBestHeuristic == endState { // mark 18
break
}
}
return path
}
}
// mark 19
var board: [[String]] = [["1","5","2"],
["4","8","3"],
["7","0","6"]] // easy board
//var hardBoard: [[String]] = [["3","2","1"],
// ["4","6","5"],
// ["7","0","8"]]
let puzzleSolver = PuzzleSolver()
let puzzleSolved = puzzleSolver.aStarSearch(start: board)
let path = puzzleSolved.boardPathStateList
for index in puzzleSolved.boardPathStateList.indices {
print("State Number \(index + 1)")
path[index].forEach({print($0)})
}
```

Let's comment each one of the marks.

- Mark 1 - Just the enum representing each direction that one piece can go.
- Mark 2 - This struct represents the list of board states of that heuristic. This means that all the past board states are stored here and the heuristic Integer value.
- Mark 3 - The PuzzleSolver class is where all the functions and the algorithm itself will be.
- Mark 4- This is the end state of the puzzle, we will compare all the solutions with this.
- Mark 5 - This function calculate all the possible moves for any board state. And the 6. return is a list of those moves.
- Mark 6 - This function just make the move to return a new board state.
- Mark 7 - The Heuristic part is here. Our heuristic is pretty pretty simple, just calculate how many pieces are out of place. The minimum value for this function is 1 because even zero in the right position is count wrong, but this don't mess with the final result.
- Mark 8 - Here is the real algorithm function. It receives a board and return a AStarPuzzle with the heuristic of the solution and all the steps of it.
- Mark 9 - The array with the explored board states to not repeat in the feature.
- Mark 10 - The first AStarPuzzle with only the start input board state.
- Mark 11 - Now we will repeat all this steps until find the one it's equal the endState declared in the class.
- Mark 12 - A reduce operator do get the lowest heuristic value.
- Mark 13 - Remove to explore the current lowest heuristic value path from the path list.
- Mark 14 - Check if we already explored that board state.
- Mark 15 - We iterate over all the possible next moves of the board, removing the already explored ones. And we store the new ones.
- Mark 16 - Calculate the heuristic value for the path. Ex: If the path has a heuristic with value 8 and it find a new path with heuristic value 4, the total heuristic of that path would be 12. If the same path with heuristic value 8 find another next board state with the value 5, we will store it too but it would be 13 in total.
- Mark 17 - Append the new APuzzleStar to the list of the possible paths.
- Mark 18 - Check if this board state is equal the final state, so we can finish the while loop.
- Mark 19 - Test the algorithm.

After the mark 19 you have two boards, one easy to solve and one hard. The hard one can be solved easily by a iPhone because in Playground it doesn't optimize the space and became too slow.

### The greedy algorithm

With a simple change you can remove the comment *//pathList.removeAll() * and solve it with **greedy graph search algorithm**. The greedy algorithm will only choose the next best decision. It will find the answer quickly but not necessarily the best one.

When I run the hard board with the greedy algorithm it took 324 steps to find the solution. When the A* took only 21 steps but with a lot more time and memory consumption.

The result of the easy board with A* Algorithm should be:

## Conclusion

Choosing the A* search algorithm will provide you the best possible answer to you problem with the memory usage drawback. Choosing the greedy one, you may find the answer with almost zero memory cost but not necessarily the best solution.

What algorithm you will choose depends of your **problem constraints**. You can play with other algorithms and better visualization in this amazing site of eight puzzle online

This article couldn't be done without the help of my dear friend Tales Conrado because the it's him implementation, I just tweaked some variable names and some code cleanup.

That's all my people, I hope you liked this as I liked writing. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying *hello*.

Thanks for the reading and... That's all folks.

credits:

### Interested in reading more such articles from Leonardo Maia Pugliese?

Support the author by donating an amount of your choice.