6

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 ?

piotrek
  • 1,333
  • 4
  • 17
  • 35
  • `std::map` is a red-black tree, not a hash. – Jan Hudec Apr 14 '11 at 10:00
  • I now but, I think for example about: std::map , 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! :( ) – piotrek Apr 14 '11 at 10:04

3 Answers3

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.

Giovanni Funchal
  • 8,934
  • 13
  • 61
  • 110
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.

Community
  • 1
  • 1
András Szepesházi
  • 6,483
  • 5
  • 45
  • 59
  • 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. – András Szepesházi Apr 14 '11 at 10:21
  • 1
    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.). – Jan Hudec Apr 14 '11 at 10:42
  • 1
    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. – Antti Huima Apr 14 '11 at 15:14
1

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

zxc
  • 194
  • 2
  • It's by definition a hash function with collisions and can't be used to store the actual state – Antti Huima Apr 14 '11 at 15:18
  • Right, which is why you use it as a _hash function_ in a _hash table_. – zxc Apr 14 '11 at 15:20
  • 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. – zxc Apr 14 '11 at 15:22
  • 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? – Antti Huima Apr 14 '11 at 15:27
  • @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. – zxc Apr 14 '11 at 15:37