{"record":{"id":"50fa753097693b7d","repo":"TheAlgorithms/Python","slug":"algorithm-is-unable-to-find-solution","errorCode":null,"errorMessage":"Algorithm is unable to find solution","messagePattern":"Algorithm is unable to find solution","errorType":"exception","errorClass":"ValueError","httpStatus":null,"severity":"error","filePath":"graphs/a_star.py","lineNumber":63,"sourceCode":"        [0 for col in range(len(grid[0]))] for row in range(len(grid))\n    ]  # the reference grid\n    closed[init[0]][init[1]] = 1\n    action = [\n        [0 for col in range(len(grid[0]))] for row in range(len(grid))\n    ]  # the action grid\n\n    x = init[0]\n    y = init[1]\n    g = 0\n    f = g + heuristic[x][y]  # cost from starting cell to destination cell\n    cell = [[f, g, x, y]]\n\n    found = False  # flag that is set when search is complete\n    resign = False  # flag set if we can't find expand\n\n    while not found and not resign:\n        if len(cell) == 0:\n            raise ValueError(\"Algorithm is unable to find solution\")\n        else:  # to choose the least costliest action so as to move closer to the goal\n            cell.sort()\n            cell.reverse()\n            next_cell = cell.pop()\n            x = next_cell[2]\n            y = next_cell[3]\n            g = next_cell[1]\n\n            if x == goal[0] and y == goal[1]:\n                found = True\n            else:\n                for i in range(len(DIRECTIONS)):  # to try out different valid actions\n                    x2 = x + DIRECTIONS[i][0]\n                    y2 = y + DIRECTIONS[i][1]\n                    if (\n                        x2 >= 0\n                        and x2 < len(grid)\n                        and y2 >= 0","sourceCodeStart":45,"sourceCodeEnd":81,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/graphs/a_star.py#L45-L81","documentation":"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.","triggerScenarios":"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).","commonSituations":"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.","solutions":["Verify the goal cell is not a wall and lies inside the grid before searching","Test connectivity with a flood fill / BFS first if the grid is large and failures are common","Wrap the call in try/except ValueError and treat it as 'no path' rather than crashing","Check that goal and init use the same coordinate convention (row, col vs x, y)"],"exampleFix":"# before\npath = a_star_search(grid, init, goal, heuristic)\n\n# after\nif grid[goal[0]][goal[1]] == 1:  # 1 = wall\n    raise ValueError(\"goal is a wall\")\ntry:\n    path = a_star_search(grid, init, goal, heuristic)\nexcept ValueError:\n    path = None  # no route exists","handlingStrategy":"try-catch","validationCode":"rows, cols = len(grid), len(grid[0])\nin_bounds = 0 <= init[0] < rows and 0 <= init[1] < len(grid[0])\ngoal_open = 0 <= goal[0] < rows and 0 <= goal[1] < len(grid[0]) and grid[goal[0]][goal[1]] != 1\nif not (in_bounds and goal_open):\n    raise ValueError(\"init/goal invalid or goal is a wall\")","typeGuard":null,"tryCatchPattern":"try:\n    path = search(grid, init, goal, heuristic)\nexcept ValueError as exc:\n    if \"unable to find solution\" in str(exc):\n        path = None  # unreachable: degrade gracefully\n    else:\n        raise","preventionTips":["Validate goal/init cells (bounds + not a wall) before searching","For frequently failing searches, pre-check connectivity with BFS/flood fill","Keep goal coordinates in the same (row, col) convention as the grid"],"tags":["graphs","pathfinding","a-star","unreachable"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}