I want to index a set of records used for A* algorithm

Question

I currently have a problem that I'm working on.

I am trying to recreate Korf's algorithm (http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf) for solving 3x3x3 rubik's cubes.

The problem is, when generating a pattern database I want a way to only store the depth (which represents the h function in A*) of the node. My current way of identifying the nodes is by a character string that looks like this: "wwooyyrrwwooyyrrggggbbbb".

Does anyone have any ideas for how I could index my pattern database so that I don't have to store (something similar to) that monstrosity for every record?

Thanks,

T

Answer 1

You can represent your string as two 64-bit number. As I remember, there is ~10^20 states of Ribik's cube, and two int64 variables gives you 2^128 combinations. I believe there are many ways to do this, but the first thing I think about is to iterate over 1..length/2 symbols of your string and add the symbol codes (0..5) to resulting value, and multiply it by 6 every time. And repeat it with length/2..length. Two int64 variables will be better than character string I think)