Closed (visited) list in state-space search - How do I make it efficient? As part of an assignment for an AI class that I'm taking, I'm need to solve a puzzle on a 4x4 grid using breadth-first search (each element can take on 12 different values). There is a maximum of 4 moves for each state. Needless to say, after 30-or-so moves, the number of nodes (each representing a state) in the queue gets too large for most (any?) computer to handle, since many nodes are duplicates.

The solution, as far as I know, is to add all visited nodes to a "visited list." This makes it possible to compute without running out of memory, but it takes forever. Why? Because for each node that I add, I have to make sure that it's not in the list of visited nodes. For a somewhat complex puzzle, this list can get really long. Let's say the list gets to 500000 nodes, which is feasible. That means that for every new node I add to the queue, it needs to be compared to 500000 nodes to make sure that it isn't identical to any node in that list. This takes a really long time to compute. It solves the problem, but I'm pretty sure I have the wrong idea about how to approach this to actually make it efficient.

I know BFS usually isn't a very good approach to these kinds of problems, but it's part of the assignment. It's only about actually solving the puzzle, but I'm interested in knowing if there is a way to make it more efficient. In general, I mean. I'm sure that I could tailor the program to make it solve this specific puzzle much faster, but what I want to know if there's some idea that could be applied to all problems. 

Any help is greatly appreciated!
Use a hash table to store the visited list. Searching the list should take $O(1)$.