Idea for keep information about visited states

Question

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:
Puzzles:

State 1
1 2
3 0

State 2
1 3
0 2

I keep in my tree:

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 ?

Answer 1

Suppose that you are only interested in solving puzzles X*Y where X, Y <= 16. I'd represent the state of the puzzle by an array of X*Y bytes in which each byte gives the value of a square in the puzzle. Using bytes instead of a BigInteger in a weird base will probably give you faster access and modification times because bit-arithmetic tends to be slow and will probably not be good overall approach in terms of memory/speed tradeoff.

template<unsigned X, unsigned Y>
class PuzzleState {
    unsigned char state[X*Y];
    public:
    void set(unsigned x, unsigned y, unsigned char v) {
        state[x+X*y] = v;
    }
    unsigned get(unsigned x, unsigned y) {
        return state[x+X*y];
    }
    bool operator<(const PuzzleState<X, Y>& other) const {
        return memcmp(state, other.state, X*Y) < 0;
    }
};

And then just use a std::set<PuzzleState<8,8 > with the insert and find methods. After testing if performance is still not appropriate, you can throw a hashtable instead of the std::set with a simple hash function, such as Rolling hash.

Answer 2

I'd represent a single state as a BigInteger number (a c++ implementation available here, or if you'd like to implement your own here is a thread on that, too).

Assuming you have a puzzle with (X,Y) dimensions, you'd create a number using base = X*Y, and the the digits of this number would represent the puzzle pieces flattened into one dimension.

For example:

State 1
1 2
3 0

This would be flattened into

1 2 3 0

and then converted into a base 4 number like:

state = (1 * (4^3)) + (2 * (4^2)) + (3 * 4) + 0;

This would uniquely indentify any given state for any puzzle.