How do I keep track of already visited states in breadth-first search? I was trying to implement the breadth-first search (BFS) algorithm for the sliding blocks puzzle (number type). Now, the main thing I noticed is that, if you have a $4 \times 4$ board, the number of states can be as large as $16!$, so I cannot enumerate all states beforehand.

How do I keep track of already visited states? I am using a class board each class instance contains a unique board pattern and is created by enumerating all possible steps from the current step.

I searched on the net and, apparently, they do not go back to the just-completed previous step, BUT we can go back to the previous step by another route too and then again re-enumerate all steps which have been previously visited. 

So, how to keep track of visited states when all the states have not been enumerated already? Comparing already present states to the present step will be costly.
Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.

However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an absurd amount of memory.

To fix this, don't use BFS. It's intractable for all but the simplest of problems, because it requires both time and memory that are exponential in the distance to the nearest goal state.

A much more memory-efficient algorithm is iterative deepening. It has all the desirable properties of BFS, but uses only O(n) memory, where n is the number of moves to reach the nearest solution. It might still take a while, but you'll hit memory limits long before CPU-related limits.

Better still, develop a domain specific heuristic, and use A* search. This should require you to examine only a very small number of nodes, and allow the search to complete in something much closer to linear time.