Data structure for Rush Hour solver taboo list

Question

I'm using Breadth First Search to solve a rush hour game. It works fine, but it takes really long on difficult boards. I am using a taboo list to avoid states I already discovered, to avoid insane memory usage and improve the run time.

I think this taboo list is the main cause of the long run time. It does drastically improve the time compared to normal BFS, but it's still too slow. Currently I'm using a normal list (C#'s List and the List.Contains method). I'm sure there are better options.

I'm storing my boards as a list of Cars + a width, height and target point (where your car should end up). a Car is stored as 2 points (top-left and bottom-right) that completely describe the car (since they can only be placed horizontally or vertically).

Some things I can think of:

• A trie
• Something with hash codes
• Huge Dictionaries (?)

What is a good/the best data structure for my problem? Thanks for the help.

Edit 1: Pseudocode (X is the taboo list type):

void Solve(Board b)
    Queue q = {b};
    X taboo = {b};
    while (q not empty)
        Board next = q.Dequeue();
        foreach (Board succ in next.Successors)
            if (succ.IsSolved)
                PrintSolution();
                return;
            if (!taboo.Contains(succ))
                q.Enqueue(succ);
                taboo.Add(succ);
    WriteLine("No solution found");

Edit 2: The solution was using a HashSet. (see below)

Answer 1

Found the answer (or at least AN answer) thanks to other people's comments. I used C#'s HashSet datastructure with the following hash function for boards:

public override int GetHashCode()
{
    int hash = 0;
    int mul = 1;
    foreach (Car c in Cars.Values)
    {
        hash += (c.P1.X + c.P1.Y * W) * mul;
        mul += W * H;
    }
    return hash;
}

This seems to work fine and give unique hash codes for every board (correct me if I'm wrong), assuming cars are always stored in the same order and P1 represents the car's top-left point.

With this solution, I can now solve Rush Hour boards that require 50 moves in less than 0.5s, with reasonable amounts of memory usage.

Answer 2

This one is inefficient but it works for me, since my RushHour overall is pretty fast.

public string HashCode()
{
    StringBuilder str = new StringBuilder();
    foreach (Car car in this.Positions)
    {
        //#yolo
        str.Append(string.Format("#{0}({1},{2})#", car.Original, car.Vector.X, car.Vector.Y));
    }
    return str.ToString();
}