Solver Algorithm

class RingSolver:
    solving: SolvingHexGrid  # Current grid state with applied paths
    start_aspects: List[Tuple[int, int]]  # Initial aspect positions
    
    best_solution: SolvingHexGrid  # Best complete solution found
    best_solution_cost: int  # Cost of best solution (lower is better)
    
    # Depth 3: [source-dest pair][path variation][path step]
    all_paths: List[List[Tuple[List[str], List[Tuple[int, int]]]]]
    path_variation_indices: List[int]  # Current variation for each level
    next_path_index: int  # Current depth in search tree
    
    iteration_count: int  # For debugging/logging

class SolvingHexGrid(HexGrid):
    applied_paths: List[List[Tuple[str, Tuple[int, int]]]]  # (aspect, coord) pairs
    _grid_cache: Dict[Tuple[int, int], str] | None  # Cached merged state
    
    def get_value(self, coord: Tuple[int, int]) -> Optional[str]:
        if self._grid_cache is None:
            # Rebuild cache from base grid + applied paths
            self._grid_cache = {coord: aspect for coord, (aspect, _) in self.grid.items()}
            for path in self.applied_paths:
                for element, path_coord in path:
                    self._grid_cache[path_coord] = element
        return self._grid_cache[coord]
    
    def apply_path(self, path: List[Tuple[int, int]], element_path: List[str]):
        self.applied_paths.append(list(zip(element_path, path)))
        self.invalidate_cache()  # Force cache rebuild on next access

def solve(self):
    # Find all non-empty nodes that need to be connected
    self.initial_nodes = [
        coord for (coord, aspect) in self.solving
        if aspect != "Free" and aspect != "Missing"
    ]
    
    done = False
    while not done:
        done = not self.do_solver_iteration()
    
    return self.best_solution

def do_solver_iteration(self) -> bool:
    """Returns False if no next iteration is possible (search is done)"""
    self.iteration_count += 1
    target = self.initial_nodes[self.next_path_index]
    
    # Find nodes not yet connected to the target
    unconnected_nodes = self.solving.get_unconnected_filled_positions(target)
    
    if len(unconnected_nodes) == 0:
        # All nodes connected - found a complete solution!
        self.report_solution()
        return self.alternate_previous_path()  # Try to find better solutions
    
    # Find all possible paths from target to unconnected nodes
    new_paths = self.solving.pathfind_both_to_many(target, unconnected_nodes)
    
    if len(new_paths) == 0:
        # Dead end - backtrack
        return self.alternate_previous_path()
    
    # Pruning: Skip if even the cheapest path would exceed best known cost
    min_extra_length = min([len(path[0]) for path in new_paths]) - 2
    if self.solving.calculate_cost() + min_extra_length * 1.5 >= self.best_solution_cost:
        return self.alternate_previous_path()
    
    # Sort paths by aspect cost (cheapest first)
    new_paths.sort(key=lambda x: calculate_cost_of_aspect_path(x[0]))
    
    # Apply the best path and continue
    self.all_paths.append(new_paths)
    initial_elem_path, initial_board_path = new_paths[0]
    self.solving.apply_path(initial_board_path, initial_elem_path)
    self.path_variation_indices.append(0)
    self.next_path_index += 1
    
    return True

def pathfind_board_lengths_to_many(self, start: Coordinate, ends: List[Coordinate], n_list: List[int]):
    paths_many: List[List[List[Coordinate]]] = [[] for _ in ends]
    end_to_info = {end: (i, n) for i, (end, n) in enumerate(zip(ends, n_list))}
    
    stack = [(start, [start])]
    
    while stack:
        current_node, current_path = stack.pop()
        
        # Pruning: Can we even reach any end from here?
        can_reach_any = False
        for i, end in enumerate(ends):
            distance = HexGrid.calculate_distance(current_node, end)
            if distance <= n_list[i] - len(current_path):
                can_reach_any = True
                break
        if not can_reach_any:
            continue
        
        for neighbor in self.get_neighbors(current_node):
            if neighbor in current_path:
                continue
            
            new_path = current_path + [neighbor]
            
            # Check if we reached a target with correct length
            if neighbor in end_to_info:
                i, curr_n = end_to_info[neighbor]
                if len(new_path) == curr_n:
                    paths_many[i].append(list(new_path))
            
            # Only traverse through free spaces
            if self.get_value(neighbor) == "Free":
                stack.append((neighbor, new_path))
    
    return paths_many

def pathfind_both_to_many(self, start: Tuple[int, int], ends: List[Tuple[int, int]]):
    # First, find shortest board paths
    shortest_path_list = self.pathfind_board_shortest_to_many(start, ends)
    
    # Filter to reachable ends only
    reachable_ends = []
    lengths = []
    for i, path in enumerate(shortest_path_list):
        if path is not None:
            reachable_ends.append(ends[i])
            lengths.append(len(path))
    
    if len(reachable_ends) == 0:
        return []  # No paths exist
    
    # Find paths of exact lengths
    paths = self.pathfind_both_lengths_to_many(start, reachable_ends, lengths)
    
    # Also try paths one step longer for more options
    if len(paths) < 5:
        lengths_plus_one = [length + 1 for length in lengths]
        paths.extend(self.pathfind_both_lengths_to_many(start, reachable_ends, lengths_plus_one))
    
    return paths

def get_connected_positions(self, start: Coordinate) -> set[Coordinate]:
    # Check cache first
    for connected_set in self.connected_positions_cache:
        if start in connected_set:
            return connected_set
    
    # Not cached - compute via flood fill over paths
    return self._populate_connected_positions_cache(start)

def _populate_connected_positions_cache(self, start: Coordinate) -> set[Coordinate]:
    connected: set[Coordinate] = {start}
    
    changes = True
    while changes:
        changes = False
        for path in self.applied_paths:
            # Check if either end of this path is already connected
            if path[0][1] in connected:
                other = path[-1][1]
            elif path[-1][1] in connected:
                other = path[0][1]
            else:
                continue
            
            if other not in connected:
                changes = True
                # Add all coordinates in this path to connected set
                for _, coord in path:
                    connected.add(coord)
    
    self.connected_positions_cache.append(connected)
    return connected

def alternate_previous_path(self) -> bool:
    """Returns True if successful, False if search is exhausted"""
    if self.next_path_index == 0:
        raise Exception("Pathfinding failed on very first path")
    
    # Keep backtracking until we find a level with untried alternatives
    while (self.path_variation_indices[self.next_path_index - 1] 
           == len(self.all_paths[self.next_path_index - 1]) - 1):
        if not self.backtrack_hard():
            return False  # Search exhausted
    
    # Try next variation at this level
    self.path_variation_indices[self.next_path_index - 1] += 1
    
    current_elem_path, current_board_path = self.all_paths[
        self.next_path_index - 1
    ][self.path_variation_indices[self.next_path_index - 1]]
    
    self.solving.applied_paths[self.next_path_index - 1] = list(
        zip(current_elem_path, current_board_path)
    )
    self.solving.invalidate_cache()
    return True

def backtrack_hard(self):
    """Returns False if there's nothing to backtrack to (search is done)"""
    self.next_path_index -= 1
    
    if self.next_path_index == 0:
        log.info("Done! Lowest Solution cost is %s", self.best_solution_cost)
        return False
    
    # Remove the failed path attempt
    self.path_variation_indices.pop()
    self.solving.applied_paths.pop()
    self.all_paths.pop()
    return True

def calculate_cost(self) -> int:
    current_sum = 0
    for path in self.applied_paths:
        for value, _ in path:  # value is the aspect name
            if value in aspect_costs and aspect_costs[value] is not None:
                current_sum += aspect_costs[value]
    return current_sum

def report_solution(self):
    new_cost = self.solving.calculate_cost()
    log.debug("Found a solution of cost %s at iteration %s", new_cost, self.iteration_count)
    
    if new_cost < self.best_solution_cost:
        log.debug("Found a new best solution of cost %s", new_cost)
        self.best_solution = self.solving.copy()  # Deep copy
        self.best_solution_cost = new_cost