pub fn solve_priority_promotion<G: PG>(game: &G, compute_strategy: bool) -> ([Set; 2], Option<[Strategy; 2]>) {

    if compute_strategy {

        let (solution, strategy) = solve_priority_promotion_impl::<G, Strategy>(game);

        (solution, Some(strategy))

        let (solution, _) = solve_priority_promotion_impl::<G, ()>(game);

        (solution, None)

}

fn solve_priority_promotion_impl<G: PG, S: Strat>(game: &G) -> ([Set; 2], [S; 2]) {

    debug_assert!(

        game.is_total(),

    let mut solver = PriorityPromotionSolver::new(game);

    let strategy = solver.solve::<S>();

    let mut w0 = bitvec![usize, Lsb0; 0; game.num_of_vertices()];

    let mut w1 = bitvec![usize, Lsb0; 0; game.num_of_vertices()];

    let mut s0 = S::new();

    let mut s1 = S::new();

    for v in game.iter_vertices() {

        let prio = solver.region_function[*v];

        debug_assert!(prio.is_none(), "All vertices should be solved");

        let winner = solver.final_winner[*v];

        match winner {

                w0.set(*v, true);

                if game.owner(v) == Player::Even

                    && let Some(target) = strategy.get(v)

                {

                    s0.set(v, target);

                }

                w1.set(*v, true);

                if game.owner(v) == Player::Odd

                    && let Some(target) = strategy.get(v)

                {

                    s1.set(v, target);

                }

    ([w0, w1], [s0, s1])

}

    fn new(game: &'a G) -> Self {

        let num_vertices = game.num_of_vertices();

        let mut lowest_region = Priority::new(0);

        let mut region_function = vec![None; num_vertices];

        let mut unsolved = Vec::with_capacity(num_vertices);

        for v in game.iter_vertices() {

            let prio = game.priority(v);

            region_function[*v] = Some(prio);

            unsolved.push(v);

            lowest_region = lowest_region.max(prio);

        }

        let mut regions = vec![0usize; lowest_region.value() + 1];

        for &r in &region_function {

            if let Some(prio) = r {

                regions[prio.value()] += 1;

            }

        PriorityPromotionSolver {

            game,

            predecessors: Predecessors::new(game),

            region_function,

            unsolved,

            regions,

            todo: VecDeque::new(),

            promotions: 0,

            dominions: 0,

            final_winner: vec![Player::Even; num_vertices],

        }

    }

    fn solve<S: Strat>(&mut self) -> S {

        let mut strategy = S::new();

        let mut prio = self.next_priority(Priority::new(self.regions.len() - 1));

            self.query(&mut strategy, prio);

            if self.is_open(prio, true) {

                debug!("Newly computed region is open in the subgame, with p = {}", prio);

                self.print_region(prio);

                prio = self.next_priority(Priority::new(prio.value().saturating_sub(1)));

            } else if !self.is_open(prio, false) {

                debug_assert!(self.todo.is_empty());

                for &v in &self.unsolved {

                    if self.region_function[*v] == Some(prio) {

                        self.todo.push_back(v);

                    }

                self.compute_attractor(&mut strategy, prio, false);

                debug!("Found the dominion D, with p = {}", prio);

                self.print_region(prio);

                let winner = Player::from_priority(&prio);

                for v in self.game.iter_vertices() {

                    if self.region_function[*v] == Some(prio) {

                        self.final_winner[*v] = winner;

                    }

                self.unsolved.clear();

                self.regions.fill(0);

                self.dominions += 1;

                for v in self.game.iter_vertices() {

                    if self.region_function[*v] == Some(prio) {

                        // Assign a special region indicating that it's solved.

                        self.region_function[*v] = None;

                    } else if self.region_function[*v].is_some() {

                        let original_prio = self.game.priority(v);

                        self.region_function[*v] = Some(original_prio);

                        strategy.remove(v);

                        // Add the not solved vertices to the unsolved set and add vertices to their region.

                        self.unsolved.push(v);

                        self.regions[original_prio.value()] += 1;

                    }

                if self.unsolved.is_empty() {

                    break; // Stop the algorithm, as all the vertices were solved.

                }

                prio = self.next_priority(Priority::new(self.regions.len() - 1));

                debug!("Promoted dominion D, with p = {}", prio);

                prio = self.promote_sub_dominion(&mut strategy, prio);

                debug!(" to {}", prio);

                self.print_region(prio);

        debug!(

        strategy

    }

    fn query<S: Strat>(&mut self, strategy: &mut S, prio: Priority) {

        debug_assert!(self.todo.is_empty());

        for &v in &self.unsolved {

            if self.region_function[*v] == Some(prio) {

                self.todo.push_back(v);

            }

        self.compute_attractor(strategy, prio, true);

    }

    fn compute_attractor<S: Strat>(&mut self, strategy: &mut S, prio: Priority, in_subgraph: bool) {

        let alpha = Player::from_priority(&prio);

        while let Some(w) = self.todo.pop_front() {

            for v in self.predecessors.predecessors(w) {

                if self.region_function[*v] == Some(prio)

                    || self.region_function[*v].is_none()

                    || (in_subgraph && self.region_function[*v].is_some_and(|region| region > prio))

                    continue;

                }

                if self.game.owner(v) == alpha {

                    // sigma(v) = w, a valid strategy for alpha is to pick a successor in A.

                    strategy.set(v, w);

                } else {

                    let is_subset = self.game.outgoing_edges(v).all(|edge| {

                        let x = edge.to();

                        if self.region_function[*x] == Some(prio) || self.region_function[*x].is_none() {

                            return true;

                        }

                        if self.region_function[*x].is_some_and(|region| region < prio) || !in_subgraph {

                            return false;

                        }

                        true

                    });

                    if !is_subset {

                        continue; // not in the attractor set yet!

                    }

                let old_region = self.region_function[*v].expect("Unsolved vertices must have a region");

                self.regions[old_region.value()] -= 1;

                self.regions[prio.value()] += 1;

                self.region_function[*v] = Some(prio);

                self.todo.push_back(v);

        for &v in &self.unsolved {

            if self.region_function[*v] == Some(prio) && self.game.owner(v) == alpha && strategy.get(v).is_none() {

                for edge in self.game.outgoing_edges(v) {

                    let w = edge.to();

                    if self.region_function[*w] == Some(prio) {

                        strategy.set(v, w);

                        break;

                    }

            }

    }

    fn is_open(&self, prio: Priority, in_subgraph: bool) -> bool {

        let alpha = Player::from_priority(&prio);

        for &v in &self.unsolved {

            if self.region_function[*v] == Some(prio) {

                if self.game.owner(v) != alpha {

                    for edge in self.game.outgoing_edges(v) {

                        let u = edge.to();

                        if self.region_function[*u].is_some()

                            && ((in_subgraph && self.region_function[*u].is_some_and(|region| region < prio))

                                || (!in_subgraph && self.region_function[*u] != Some(prio)))

                            return true;

                        }

                    let is_open = self

                        .game

                        .outgoing_edges(v)

                        .all(|edge| self.region_function[*edge.to()] != Some(prio));

                    if is_open {

                        return true;

                    }

            }

        false

    }

    fn promote_sub_dominion<S: Strat>(&mut self, strategy: &mut S, prio: Priority) -> Priority {

        let alpha = Player::from_priority(&prio);

        let mut promotion = Priority::new(self.regions.len() - 1);

        for &v in &self.unsolved {

            if self.region_function[*v] == Some(prio) && self.game.owner(v) != alpha {

                for edge in self.game.outgoing_edges(v) {

                    let u = edge.to();

                    if let Some(region) = self.region_function[*u]

                        && region > prio

                    {

                        promotion = promotion.min(region);

                    }

            }

        self.promotions += 1;

        for &v in &self.unsolved {

            if self.region_function[*v] == Some(prio) {

                // Promote the current region to the promotion priority.

                self.regions[prio.value()] -= 1;

                self.region_function[*v] = Some(promotion);

                self.regions[promotion.value()] += 1;

            } else if self.region_function[*v].is_some_and(|region| region < promotion) {

                // Reset all vertices higher to the original priorities, remove the strategy.

                let old_region = self.region_function[*v].expect("Unsolved vertices must have a region");

                self.regions[old_region.value()] -= 1;

                let original_prio = self.game.priority(v);

                self.region_function[*v] = Some(original_prio);

                strategy.remove(v);

                self.regions[original_prio.value()] += 1;

            }

        promotion

    }

    fn print_region(&self, prio: Priority) {

        if log::log_enabled!(log::Level::Trace) {

        }

    }

    fn next_priority(&self, prio: Priority) -> Priority {

        let mut p = prio.value();

        while self.regions[p] == 0 {

            assert!(p > 0, "next_priority went out of bounds");

            p -= 1;

        Priority::new(p)

    }

    fn test_random_priority_promotion_solver() {

        random_test(100, |rng| {

            let mut files = DumpFiles::new("test_random_priority_promotion_solver");

            let game = random_parity_game(rng, true, 100, 5, 3);

            files.dump("input.pg", |writer| write_pg(writer, &game)).unwrap();

            let (solution, strategy) = solve_priority_promotion(&game, true);

            verify_solution(&game, &solution, &strategy.unwrap());

        });

    }

    fn test_priority_promotion_matches_zielonka() {

        random_test(100, |rng| {

            let game = random_parity_game(rng, true, 50, 4, 3);

            let (pp_solution, _) = solve_priority_promotion(&game, false);

            let (zielonka_solution, _) = solve_zielonka(&game, false);

            assert_eq!(

                pp_solution[0], zielonka_solution[0],

            assert_eq!(

                pp_solution[1], zielonka_solution[1],

        });

    }