search

digimokan / cpp-sliding-eight-puzzle

Sliding Eight-Puzzle solver
0 stars 0 forks source link

FrontierQueue::prune_removed_nodes() assert crashes program #2

Open digimokan opened 5 years ago

digimokan commented 5 years ago

Description

When running the program with ./eight-puzzle -b "567408321" "123804765" (a 15-step solution), the assert below fails. Why? It seems like the invariant of matching board_node_lookup and nodes_on_queue should hold at all times....

void FrontierQueueBase::prune_removed_nodes () {
   . . .
  assert(this->board_node_lookup.not_contains(next_node->get_board()));
  this->pop_logic();
   . . .
}

Source Files

FrontierQueueBase.cpp

Steps To Reproduce

Add the above assert in prune_removed_nodes(), then run the program in debug with the above arguments.

digimokan commented 5 years ago

Note: program does run if you remove assert, BUT it produces the bug in Issue #5 (i.e. the incorrect BFS result). So probably, this assert shouldn't be firing.

digimokan commented 5 years ago

Possibly, the issue is using std::shared_ptr as the hash key in the many unordered_map, set, etc data structures used in various classes. Surely, a value of std::shared_ptr isn't unique over the lifetime of a program.

Possible test case to give weight to this hypothesis: create a new test based on "push ABCD, pop ABC, push EF, pop D" from FrontierQueueBase_test.cpp. Instead of creating many nodes all in one go, create some, push them then pop them, create some more, repeat.

Possible solution: use Boost::uuids everywhere instead of shared_ptr.