Using valgrind I see:

$ valgrind --leak-check=full --num-callers=50 --show-reachable=no --show-possibly-lost=no --track-origins=yes --trace-children=yes --read-var-info=yes hex-a-hop

==17701== 1,151 bytes in 100 blocks are definitely lost in loss record 688 of 762
==17701==    at 0x483950F: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17701==    by 0x113AC1: SetSolution (savestate.h:141)
==17701==    by 0x113AC1: LoadSave (savestate.h:84)
==17701==    by 0x113AC1: SaveState::LoadSave(_IO_FILE*, bool) (savestate.h:281)
==17701==    by 0x115357: TitleMenu::TitleMenu() (menus.h:986)
==17701==    by 0x11A030: HexPuzzle::ResetLevel() (hex_puzzzle.cpp:1635)
==17701==    by 0x11A4F1: HexPuzzle::_LoadSave(_IO_FILE*, bool) (hex_puzzzle.cpp:2045)
==17701==    by 0x11AD31: HexPuzzle::LoadSave(char const*, bool) (hex_puzzzle.cpp:1830)
==17701==    by 0x11DDDD: LoadMap (hex_puzzzle.cpp:2453)
==17701==    by 0x11DDDD: LoadMap (hex_puzzzle.cpp:2447)
==17701==    by 0x11DDDD: HexPuzzle::HexPuzzle() (hex_puzzzle.cpp:2444)
==17701==    by 0x11E19F: StateMaker<HexPuzzle>::Create() (state.h:216)
==17701==    by 0x10ECAB: GetNew (state.h:198)
==17701==    by 0x10ECAB: main (gfx.cpp:273)

Note: I start the game and then exit

as you can see the last bestSolution allocation is never free.
I have added a destructor to the class for free the memory.

Ciao
Davide