Holy Swift

Holy Swift

Solving Eight Puzzle with A* Algorithm in Swift

Solving Eight Puzzle with A* Algorithm in Swift

A great graph algorithm in Swift

Subscribe to my newsletter and never miss my upcoming articles

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:

Screen Shot 2021-06-30 at 15.17.58.png

Or this: Screen Shot 2021-06-30 at 15.19.41.png

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:

Screen Shot 2021-06-30 at 15.36.53.png

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:

Screen Shot 2021-06-30 at 15.38.28.png

And this position:

Screen Shot 2021-06-30 at 15.39.13.png

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

Screen Shot 2021-06-30 at 15.44.35.png

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.

Screen Shot 2021-06-30 at 15.33.25.png

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.

  1. Mark 1 - Just the enum representing each direction that one piece can go.
  2. 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.
  3. Mark 3 - The PuzzleSolver class is where all the functions and the algorithm itself will be.
  4. Mark 4- This is the end state of the puzzle, we will compare all the solutions with this.
  5. Mark 5 - This function calculate all the possible moves for any board state. And the 6. return is a list of those moves.
  6. Mark 6 - This function just make the move to return a new board state.
  7. 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.
  8. 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.
  9. Mark 9 - The array with the explored board states to not repeat in the feature.
  10. Mark 10 - The first AStarPuzzle with only the start input board state.
  11. Mark 11 - Now we will repeat all this steps until find the one it's equal the endState declared in the class.
  12. Mark 12 - A reduce operator do get the lowest heuristic value.
  13. Mark 13 - Remove to explore the current lowest heuristic value path from the path list.
  14. Mark 14 - Check if we already explored that board state.
  15. Mark 15 - We iterate over all the possible next moves of the board, removing the already explored ones. And we store the new ones.
  16. 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.
  17. Mark 17 - Append the new APuzzleStar to the list of the possible paths.
  18. Mark 18 - Check if this board state is equal the final state, so we can finish the while loop.
  19. 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:

Screen Shot 2021-07-03 at 10.03.43.png

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:

title image

first puzzle image

second puzzle image

Puzzle and graph image

Interested in reading more such articles from Leonardo Maia Pugliese?

Support the author by donating an amount of your choice.

 
Share this