Idea for keep information about visited states

I making now 15-puzzle solver (in c++), but instead of only 15-puzzle, my program must to solve also 3x4 puzzles, 8x8 puzzles, etc... - > X x Y puzzles. I must somehow keep information about visited states, my first idea was to make tree, for example:
Головоломки:

Состояние 1
1 2
3 0

Состояние 2
1 3
0 2

Я храню в своем дереве:

root-> 1-> 2-> 3-> 0
\ _
\->3->0->2

This will work also for puzzle 5x3, 6x6, etc, for all puzzles

This idea works, but it waste a lot of memory, and to add node, it need some time:/ So it is very inefficient.

Next idea was to keep visited states in stl's std::map< > , but I don't know how to make good hash function - for making shortcut from puzzle state ( beacouse I don't must to store puzzle state, I need only information has been visited. Do you have any idea, for key to std::map, or other ideas to keep informations about has been state visited ?