Solve 8-tile sliding puzzle

Question

I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.

Advice on how to aproach this would be appreciated.

Code for DFS and printing omitted for clarity:

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle
{
    int state[PUZZLE_LENGTH];
    int gapLocation;
};

struct breadthPuzzle
{
    Puzzle puzzle;
    int parent;
};

const Puzzle SOLVED_PUZZLE = { { 1,2,3,4,5,6,7,8,EMPTY } };

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)
{
    int inversions = 0;

    for ( int i = 0; i < PUZZLE_LENGTH; i++ )
        for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
            if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
                inversions++;

    // If the amount of inversions is even the puzzle can be solved
    return inversions % 2 == 0;

}

// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)
{
    for ( int length = 0; length < PUZZLE_LENGTH; length++ )
        if ( puz1.state[length] != puz2.state[length] ) return false;
    return true;
}

bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)
{
    for ( int i = 0; i < currentRoute.size(); i++ )
        if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
            return true;
    return false;
}

// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)
{
    return puzzleTheSame(SOLVED_PUZZLE, solution);
}

bool canNorth(int gapLocation)
{
    return gapLocation > 2;
}

bool canEast(int gapLocation)
{
    return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);
}

bool canSouth(int gapLocation)
{
    return gapLocation < 6;
}

bool canWest(int gapLocation)
{
    return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);
}

int north(int gap)
{
    return gap - 3;
}

int east(int gap)
{
    return gap + 1;
}

int south(int gap)
{
    return gap + 3;
}

int west(int gap)
{
    return gap - 1;
}

Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)
{
    int temp = currentPuzzle.state[pos];
    currentPuzzle.state[currentPuzzle.gapLocation] = temp;
    currentPuzzle.state[pos] = EMPTY;
    currentPuzzle.gapLocation = pos;
    return currentPuzzle;
}

void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)
{
    Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

    if ( !puzzleExists(currentPuzzle, currentRoute) )
    {
        breadthPuzzle candidate{ currentPuzzle, i };
        currentRoute.push_back(candidate);
    }
}

void breadthFirst(Puzzle initalPuzzle)
{
    // Origin has no parent, thus -1 as start.
    vector<breadthPuzzle> breadthVector = { { initalPuzzle, -1 } };
    int i = 0;

    while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
    {
        Puzzle currentPuzzle = breadthVector[i].puzzle;
        int gapLocation = currentPuzzle.gapLocation;

        if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
        if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
        if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
        if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
        i++;
    }
}

int main()
{
    Puzzle toSolve = { {1,2,3,4,6,5,8,7,EMPTY}, 8 };
    //Breadth-First: Duration in seconds = 72;
    //Depth-First: Duration in seconds = 15;

    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    if ( isSolvable(toSolve) )
    {
        cout << "Puzzle Solvable\n";
        breadthFirst(toSolve);
    }
    else
        cout << "Puzzle insolvable, stopping\n";

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto durationSec = duration_cast<seconds>(t2 - t1).count();

    cout << "Duration in seconds of function: " << durationSec << endl;
}

Answer 1

Here's the code you want to speed up:

// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)
{
    for ( int length = 0; length < PUZZLE_LENGTH; length++ )
        if ( puz1.state[length] != puz2.state[length] ) return false;
    return true;
}

bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)
{
    for ( int i = 0; i < currentRoute.size(); i++ )
        if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
            return true;
    return false;
}

// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)
{
    return puzzleTheSame(SOLVED_PUZZLE, solution);
}

It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.

For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.

bool operator==(const Puzzle& puz1, const Puzzle& puz2)
{
    return std::equal(std::begin(puz1.state), std::end(puz1.state),
                      std::begin(puz2.state), std::end(puz2.state));
}

bool puzzleExists(const Puzzle& currentPuzzle,
                  const std::vector<breadthPuzzle>& currentRoute)
{
    for (auto&& elt : currentRoute) {
        if (elt.puzzle == currentPuzzle) {
            return true;
        }
    }
    return false;
}

We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!

bool isSolved(const Puzzle& puzzle)
{
    return puzzle == SOLVED_PUZZLE;
}

---

Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!

bool operator<(const Puzzle& puz1, const Puzzle& puz2)
{
    return std::lexicographical_compare(
        std::begin(puz1.state), std::end(puz1.state),
        std::begin(puz2.state), std::end(puz2.state));
}

bool puzzleExistsInSet(const Puzzle& puzzle,
                       const std::set<Puzzle>& seenPuzzles)
{
    return seenPuzzles.find(puzzle) != seenPuzzles.end();
}

Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.

---

Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.

But its one caller calls it four times! Can we fix that?

    if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
    if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
    if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
    if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));

Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:

for (auto&& m : { north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) }) {
    if (isLegalMove(m)) {
        makeMove(breadthVector, i, m);
    }
}

Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.