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 ?

Glaswegian

std::map is a red-black tree, not a hash. – Entozoic

I now but, I think for example about: std::map<int> , and then I can puzzles state 4x4 "compress" to one int, but for bigger states it will don't work ( for example 8x8, then i have number max 64! :( ) – Glaswegian

Answer 1

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.

Kithara

Hmm giving this a second thought, this approach will not be very memory efficient at a 15x15 or even larger puzzle. I'm curious what others will suggest. – Chrissa

It is more memory-efficient than storing it in a vector (which is equivalent to using base 2^32), not even mentioning a list. In fact it's the minimal way to store the state. Than it depends on the overhead of the big integer implementation (e.g. allocation from a pool will save quite some overhead compared to plain new etc.). – Entozoic

It's not minimal because the states are permutations of numbers 1..XY (using number XY to represent the empty slot), so there are (XY)! states (only 1/2 of them are reachable, though) but the power encoding allows for (XY)^(XY) states, which is more. E.g. 15-puzzle has 2^44 possible states (not all reachable), but 16^16 (power encoding) is equal to 2^128, so this encoding wastes more than 80 bits. – Garrik

Answer 2

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.

Distort

Answer 3

Zobrist hashing is pretty much ubiquitous in programs that play abstract games.

Hence

It's by definition a hash function with collisions and can't be used to store the actual state – Garrik

Right, which is why you use it as a hash function in a hash table. – Hence

Also, if you run the hash out to say 160 bits, then the probability of a collision is less than that of cosmic rays screwing up the computation in some other way. – Hence

Well, if you are solving a 8x8 puzzle it has 2^296 distinct states, so a 160-bit hash function would have quite a many collisions. For 4x4, you can store the whole state trivially in 2^128 bits (see answer by A.S.), so what's the point of using a hash value that is bigger then the actual state representation? – Garrik

@antti.huima Obviously there are collisions, but since the Zobrist hash is 2-universal and the solver is oblivious to the hash vectors, they are extremely unlikely to occur in a reasonable amount of time. – Hence