Search code examples
c++stlsliding-tile-puzzle

8 Puzzle: Sorting STL Heap/Priorirty Queue containing pointers to object by member variable

I'm working on implementing a Best-First Search algorithm to solve an 8-Puzzle problem for an assignment. Based on the requirements, it must be implemented using a (min) Priority Queue or Heap located in the Standard Template Library (STL).

I understand that it would be useful to use either data structure to organise expanded puzzle states by best heuristic cost (ie. the smallest cost).

Beginning with a 3x3 matrix (implemented using an array)

Puzzle *current=new Puzzle(initialState, goalState);

Each new puzzle state (an object) is created using:

Puzzle *next=(current->moveDown());
Puzzle *next=(current->moveRight());
Puzzle *next=(current->moveUp());
Puzzle *next=(current->moveRight());

I'd like to .push(next) onto a (Min) Priority Queue or Heap (of Puzzle*), sorted according to next->FCost.

Generically, is there a way that I can use either of these STL data structures to contain pointers to objects - sorted by a member variable (FCost) specific to each object?

Solution

  • Yes, you can specify a custom compare function for priority_queue

    auto cmp = [](Puzzle* a, Puzzle* b) { 
    return a->FCost > b->FCost;
};

std::priority_queue<Puzzle*, std::vector<Puzzle*>, decltype(cmp)> queue(cmp);