TheAlgorithms/Python · error · ValueError

Algorithm is unable to find solution

Error message

Algorithm is unable to find solution

What it means

Raised by the A* search loop (graphs/a_star.py:63) when the open list ('cell') becomes empty before the goal is reached. An empty frontier means every reachable state was expanded and none matched the goal — the search space is exhausted, so no path exists between init and goal under the given grid and movement rules.

Source

Thrown at graphs/a_star.py:63

        [0 for col in range(len(grid[0]))] for row in range(len(grid))
    ]  # the reference grid
    closed[init[0]][init[1]] = 1
    action = [
        [0 for col in range(len(grid[0]))] for row in range(len(grid))
    ]  # the action grid

    x = init[0]
    y = init[1]
    g = 0
    f = g + heuristic[x][y]  # cost from starting cell to destination cell
    cell = [[f, g, x, y]]

    found = False  # flag that is set when search is complete
    resign = False  # flag set if we can't find expand

    while not found and not resign:
        if len(cell) == 0:
            raise ValueError("Algorithm is unable to find solution")
        else:  # to choose the least costliest action so as to move closer to the goal
            cell.sort()
            cell.reverse()
            next_cell = cell.pop()
            x = next_cell[2]
            y = next_cell[3]
            g = next_cell[1]

            if x == goal[0] and y == goal[1]:
                found = True
            else:
                for i in range(len(DIRECTIONS)):  # to try out different valid actions
                    x2 = x + DIRECTIONS[i][0]
                    y2 = y + DIRECTIONS[i][1]
                    if (
                        x2 >= 0
                        and x2 < len(grid)
                        and y2 >= 0

View on GitHub (pinned to f5988cc097)

Solutions

1. Verify the goal cell is not a wall and lies inside the grid before searching
2. Test connectivity with a flood fill / BFS first if the grid is large and failures are common
3. Wrap the call in try/except ValueError and treat it as 'no path' rather than crashing
4. Check that goal and init use the same coordinate convention (row, col vs x, y)

Example fix

# before
path = a_star_search(grid, init, goal, heuristic)

# after
if grid[goal[0]][goal[1]] == 1:  # 1 = wall
    raise ValueError("goal is a wall")
try:
    path = a_star_search(grid, init, goal, heuristic)
except ValueError:
    path = None  # no route exists

rows, cols = len(grid), len(grid[0])
in_bounds = 0 <= init[0] < rows and 0 <= init[1] < len(grid[0])
goal_open = 0 <= goal[0] < rows and 0 <= goal[1] < len(grid[0]) and grid[goal[0]][goal[1]] != 1
if not (in_bounds and goal_open):
    raise ValueError("init/goal invalid or goal is a wall")

try:
    path = search(grid, init, goal, heuristic)
except ValueError as exc:
    if "unable to find solution" in str(exc):
        path = None  # unreachable: degrade gracefully
    else:
        raise

When it happens

Trigger: Goal cell sits inside a wall or in a region fully enclosed by walls; goal coordinates are outside the walkable area; a heuristic/movement configuration makes the goal unreachable (e.g. move rules that forbid reaching the goal's row/column).

Common situations: Procedurally generated mazes where walls can seal off sections; goals chosen from user input without a reachability check; changing DIRECTIONS (movement set) so previously solvable grids no longer connect; off-by-one when converting map coordinates to grid indices.

Related errors

• No path from vertex: {self.source_vertex} to vertex: {target
• Negative cycle found
• Vertex indexes must be in [0; size).
• You need to set maximum flow algorithm before.
• You should execute algorithm before using its result!

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/50fa753097693b7d. Report an issue: GitHub.