Generate the optimal solution for I 🖤 Hue, given the board current state and solved state.

hue_solve_optimal.py

class Board:
    # details omitted
    
    def solve_optimal(self):
        # self.cur_color: Dict[Tile, Color]
        #     the current board state, what color is on each tile
        
        # self.cur_placement: Dict[Color, Tile]
        #     the current board state, where each color is sitting now
        
        # self.solution_color: Dict[Tile, Color]
        #     the solved board state, what color should be on each tile
        
        # self.solution_placement: Dict[Color, Tile]
        #     the solved board state, where each color should be placed
        #     (not used here)
        
        
        unsolved_tiles = set(self.cur_color)
        cur_color = self.cur_color.copy()
        cur_placement = self.cur_placement.copy()
        
        def swap_placement(t1, t2):
            c1, c2 = cur_color[t1], cur_color[t2]
            
            cur_placement[c1], cur_placement[c2] = t2, t1
            cur_color[t1], cur_color[t2] = c2, c1
        
        result = []
        while unsolved_tiles:
            perm = []
            result.append(perm)
            
            cur = unsolved_tiles.pop()
            perm.append(cur)
            next = cur_placement[self.solution_color[cur]]
            
            while next != cur:
                
                swap_placement(cur, next)
                cur = next
                unsolved_tiles.remove(cur)
                perm.append(cur)
                next = cur_placement[self.solution_color[cur]]
        
        return result
        # result now contains a list of all the cycles on the board.
        # cycles of length 1 are solved tiles