Pattern Databases Storing all permutations

Question

I am looking for some advice on storing all possible permutations for the fringe pattern database.

So the fifteen tile problem has 16! possible permutations, however storing the values for fringe so the 0 (blank tile),3,7,11,12,13,14,15 is 16!/(16-8)! = 518,918,400 permutations.

I am looking to store all of these permutations in a datastructure along with the value of the heuristic function (which is just incremented each time a iteration of the breadth first search), so far I am doing so but very slowly and took me 5 minutes to store 60,000 which is time I don't have!

At the moment I have a structure which looks like this.

Value Pos0 Pos3 Pos7 Pos11 Pos12 Pos13 Pos14 Pos15 

Where I store the position of the given numbers. I have to use these positions as the ID for when I am calculating the heuristic value I can quickly trawl through to the given composition and retrieve the value.

I am pretty unsure about this. The state of the puzzle is represented by an array example:

int[] goalState = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} 

My question is what would be the best data structure to store these values? and the best way to retrieve them.

(This question was originally based on storing in a database, but now I want to store them in some form of local data structure - as retrieving from a database slow )

Answer 1

I can't really grasp, what special meaning do 0,3,7,11,12,13,14,15 have in your case. Is their position unchangeable? Is their position enough to identify the whole puzzle state?

Anyway, here is a general approach, you can narrow it down anytime:

As you have 16 possible states at max, I would try to use hexadecimal numbers to represent your permutations. So the state {1,2,3,6,5,4,7,8,9,10,11,12,13,14,15,0} would look like 0x123654789ABCDEF0 = 1312329218393956080. The biggest number possible would be 0xFEDCBA9876543210, which still can be stored in an unsigned long (only since Java 8) or alternatively in BigInteger (there are many examples, I would prefer this). Such number would be unique for each permutation and could be used as primary key and if you have the whole state, retrieving it from the database would be pretty fast.

//saving your permutation String state = "0xFEDCBA9876543210"; BigInteger permutationForDatabase = new BigInteger(state, 16); //and then you can insert it into database as a number  //reading your permutation char searchedCharacter = 'A';//lets say you look for tile 10 BigInteger permutation = ...;//here you read the number from the database int tilePosition = permutation.toString(16).indexOf(searchedCharacter); 

There might be a more elegant/performant solution to get the tile position (maybe some bit operation magic).

Answer 2

Each number 0-15 is a 4-bit number. You must represent 7 such numbers, making a minimum requirement of 28 bits, which is well within the 31 signed bit space of an int. Thus all permutations may be assigned, and derived from, an int.

To calculate this number, given variables a through g:

int key = a | (b << 4) | (c << 8) | (d << 12) | (e << 16) | (f << 20) | (g << 24); 

To decode (if you need to):

int a = key & 0xF; int b = key & 0xF0; int c = key & 0xF00; // etc 

Storing ints in a database is very efficient and will use minimal disk space:

create table heuristics (     key_value int not null,     heuristic varchar(32) not null -- as small as you can, char(n) if all the same length ); 

After inserting all the rows, create a covering index for super fast lookup:

create unique index heuristics_covering heuristics(key_value, heuristic); 

If you create this index before insertion, insertions will be very, very slow.

Creating the data and inserting it is relatively straightforward coding.