A* to recognize it's impossible to get to the goal

Question

I implemented A* for the 8 puzzle problem pretty much word for word to the pseudo code in the wiki article but even though I have closed I still get infinite runtime on boards that should fail.

It seems that the rate of opening new nodes is larger than closing them, since for each node about 1-4 new nodes are added to the open but only one node is moved from open to closed.

So what can be done to recognize that a given starting board has no path to the goal without waiting forever?

This is the code:

public List<KeyValuePair<GameBoard, GameBoard.MoveDirection>> Search(GameBoard startBoard, GameBoard goal)
{
    InitSearch(startBoard, goal);
    while (_open.Count > 0)
    {
        GameBoard current = LowestFScoreInOpen();
        if (current.Equals(_goal))
        {
            return ReconstructPath(current);
        }

        _open.Remove(current);
        _closed.Add(current);

        foreach (GameBoard.MoveDirection direction in Enum.GetValues(typeof(GameBoard.MoveDirection)))
        {
            GameBoard neighbor = current.MoveAndCopy(direction);
            if(neighbor == null) continue;  // invalid direction 
            if(_closed.Contains(neighbor)) continue;

            int tentativeScore = _gScore[current] + 1;
            if (!_open.Contains(neighbor))
            {
                _open.Add(neighbor);
            }
            else if (tentativeScore >= _gScore[neighbor])
            {
                continue; // already in _open and this is not a better path 
            }

            // best path so far
            _cameFrom[neighbor] = new KeyValuePair<GameBoard, GameBoard.MoveDirection>(current, direction);
            _gScore[neighbor] = tentativeScore;
            int fscore = tentativeScore + Heuristic(neighbor);
            _fScore[neighbor] = fscore;
            _sortedFScore.Enqueue(new PriorityQueueItem<GameBoard, int>(neighbor, fscore));
        }
    }

    return null; // no path found
}

Example for start and goal board with no path between them:

Start: Goal:

Full code: https://pastebin.com/v10U2J2Z

Answer 1

The problem here is not in algorithm implementation (well there might be problems with it too - did not check), but in wrong implementation of GetHashCode() for GameBoard class:

public int[,] Board { get; }
public override int GetHashCode()
{
    return Board.GetHashCode();
}

Board is array and array is a class (not struct) so it's default GetHashCode() implementation just returns some value which is guaranteed to be the same for this instance only. That means that:

var a = new int[] {1,2,3};
var b = new int[] {1,2,3};
Debug.Assert(a.GetHashCode() == b.GetHashCode());

Fails, because even though array contents are the same - those are different instances and GetHashCode returns completely different values.

That wrong GetHashCode implementation is used in critical places in your algorithm, most importantly (for this concrete problem) in closed set, which is:

HashSet<GameBoard> _closed = new HashSet<GameBoard>();

When you do

if (_closed.Contains(neighbor)) continue;

It fails to detect that closed set contains given board, even if it really does, because the only requiremet for a hash function (objects that are equal should return hash codes that are equal) is violated. So your closed set growth without bound because you add the same boards there again and again.

Easy to check with this code:

var set = new HashSet<GameBoard>();
set.Add(new GameBoard(new int[,]
{
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5},
}));
bool contains = set.Contains(new GameBoard(new int[,]
{
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5},
})); // false

To fix, do something like:

public override int GetHashCode()
{                          
     // make _flatten readonly by the way, now it's not
     return _flatten.GetHashCode();
}

And your program will terminate (will throw null reference exception, because you return null if there is no solution but don't check for this when printing solution).