Idea for storing information about visited conditions

Question

I'm doing a 15 puzzle now (in C ++), but instead of a 15 puzzle, my program should also solve 3x4 puzzles, 8x8 puzzles, etc. → X x Y puzzles. I had to somehow store information about the states visited, my first idea was to make a tree, for example:
Puzzles:

State 1
12
thirty

State 2
thirteen
0 2

I keep in my tree:

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

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

This idea works, but it spends a lot of memory and adds node, it needs some time: / This is very inefficient.

The next idea was to save the visited states in stl std :: map <>, but I do not know how to make a good hash function - to create a shortcut from the state of the puzzle (beacouse I do not have to store the state of the puzzle, I only need information You visited. Do you have an idea, std :: map or other ideas for saving state information that you visited the state?

Answer 1

I would represent one state as a BigInteger number (an available C ++ implementation is here , or if you want to implement your own here is also a stream.)

Assuming that you have a puzzle with dimensions (X, Y), you should create a number using base = X * Y, and the numbers of this number will represent parts of the puzzle flattened into one dimension.

For instance:

State 1 1 2 3 0 

It will be flattened into

 1 2 3 0 

and then converted to a base number of 4, for example:

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

This will uniquely determine any given state for any puzzle.

Answer 2

Suppose you are only interested in solving the puzzles X * Y, where X, Y <= 16. I would imagine the state of the puzzle as an array of X * Y bytes, in which each byte gives a square value in the puzzle. Using bytes instead of BigInteger in a strange database is likely to give you faster access and modification time, because bit arithmetic tends to be slow and probably not a good general approach in terms of memory / speed exchange.

 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 std::set<PuzzleState<8,8 > with the insert and find methods. After testing, if performance still does not fit, you can use the hash table instead of std::set with a simple hash function like Rolling hash .

Answer 3

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