Checking already visited states in A* solution for 8-puzzle problem

Question

I am working on a solution to the 8-puzzle problem using the A* algorithm for an university assignment, and currently working on a method to identify already visited states of the puzzle to reduce redundant operations. I could brute-force the issue and make a list of already visited states and search it for every state that is being explored, however that is very obviously inefficient. I am looking for some way to give any state of the puzzle an unique integer identifier so that I could search any state within a Boolean array and check wether it's been visited or not.

I thought of taking a similar approach to that of Godel's Incompleteness Theorem when assigning numbers to mathematical symbols, assigning prime numbers to each position of the puzzle (that way the top left position gets the number 2, the middle top position the number 3, the right top position the number 5 and so on). That way given a state of the puzzle

[[a, b, c]; [d, e, f]; [g, h, i]]

It's identifier would be given by Id = (2^a)(3^b)(5^c) and so on, however it doesn't take long to realize that these numbers get very, very big, and having an array that size would be extremely impractical from a memory standpoint (and I don't even think having an array the necessary size is even possible).

The other option was an 8-dimmensional Array with boolean values so that you could access it with the corresponding values of the permutation of the puzzle, however an 8-dimmensional array is very aesthetically unpleasing in terms of syntax and a pain in the rear just to declare the variable.

Is there a way that I can assign an unique integer identifier to any given state of the puzzle so that I could recognize if it's already been visited in an instantaneous manner instead of having to search for it in a list of already visited states?

Answer 1

You need a hash table, which offers O(1) search complexity.

As for a unique identifier, you can use some sort of hash, e.g.:

id = state[0][0]
id = id * 37 + state[0][1]
id = id * 37 + state[0][2]
// and so on for every number in state

For 3x3 board it would be sufficient to represent every state with unique integer value, which will play nicely with a hash table.