9
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate. \$\endgroup\$ – Toby Speight Aug 10 '18 at 12:15
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense \$\endgroup\$ – Hirtol Aug 9 '18 at 20:39
  • 1
    \$\begingroup\$ In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context. \$\endgroup\$ – Quuxplusone Aug 10 '18 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.