color_grid_game.solvers package

Submodules

color_grid_game.solvers.blossom module

class color_grid_game.solvers.blossom.SolverBlossom(grid: Grid, rules='original rules')

Bases: Solver

A solver that uses weighted matching to minimize the score in a grid. Adapted to use a NetworkX graph instead of an adjacency dictionary.

Methods

run()	Builds a NetworkX graph and uses the max_weight_matching algorithm from NetworkX.
score()	Computes the score of the list of pairs in self.pairs.

run()

Builds a NetworkX graph and uses the max_weight_matching algorithm from NetworkX.

Returns:

list of tuple

A list of pairs of cells, each represented as a tuple of tuples.

Raises:

ValueError

If the graph is empty or if pairs are invalid.

color_grid_game.solvers.empty module

class color_grid_game.solvers.empty.SolverEmpty(grid: Grid, rules='original rules')

Bases: Solver

A subclass of Solver that does not implement any solving logic.

Methods

run()	Placeholder method for running the solver.
score()	Computes the score of the list of pairs in self.pairs.

run()

Placeholder method for running the solver. Does nothing.

This method is intended to be overridden by subclasses that implement specific solving algorithms.

color_grid_game.solvers.ford_fulkerson module

class color_grid_game.solvers.ford_fulkerson.SolverFordFulkerson(grid: Grid, rules='original rules')

Bases: Solver

A subclass of Solver that implements a bipartite matching algorithm to find pairs.

Methods

bfs(graph, s, t)	Performs a BFS to find a path from source 's' to sink 't' in the graph.
ford_fulkerson(graph, even_cells, odd_cells)	Computes the maximum flow (maximum matching) in the bipartite graph using the Ford-Fulkerson method.
reconstruct_path(parents, s, t)	Reconstructs the path from 's' to 't' using the parents dictionary.
run()	Runs the bipartite matching algorithm to find pairs of cells.
score()	Computes the score of the list of pairs in self.pairs.

static bfs(graph: dict, s: str, t: str) → list[int]

Performs a BFS to find a path from source ‘s’ to sink ‘t’ in the graph.

Parameters:

graphdict

The graph represented as an adjacency list.

sstr

The source node.

tstr

The sink node.

Returns:

list of int

The path from ‘s’ to ‘t’ if found, otherwise None.

Raises:

ValueError

If the graph is empty or if s or t is not in the graph.

classmethod ford_fulkerson(graph: dict, even_cells: set, odd_cells: set) → list[tuple[tuple[int, int], tuple[int, int]]]

Computes the maximum flow (maximum matching) in the bipartite graph using the Ford-Fulkerson method.

Parameters:

graphdict

The graph represented as an adjacency list.

Returns:

list of tuple

The maximum matching as a list of pairs of cells.

Raises:

ValueError

If the graph is empty or if even_cells or odd_cells is empty.

static reconstruct_path(parents: dict, s: str, t: str) → list[int]

Reconstructs the path from ‘s’ to ‘t’ using the parents dictionary.

Parameters:

parentsdict

A dictionary where parents[v] is the predecessor of v on the path from ‘s’ to ‘v’.

sstr

The source node.

tstr

The sink node.

Returns:

list of int

The reconstructed path from ‘s’ to ‘t’.

Raises:

ValueError

If the path cannot be reconstructed.

run() → list[tuple[tuple[int, int], tuple[int, int]]]

Runs the bipartite matching algorithm to find pairs of cells.

Returns:

list of tuple

A list of pairs of cells, each represented as a tuple of tuples.

Raises:

ValueError

If any cell in pairs is invalid.

color_grid_game.solvers.greedy module

class color_grid_game.solvers.greedy.SolverGreedy(grid: Grid, rules='original rules')

Bases: Solver

A subclass of Solver that implements a greedy algorithm to find pairs.

Methods

run()	Runs the greedy algorithm to find pairs of cells.
score()	Computes the score of the list of pairs in self.pairs.

run() → list[tuple[tuple[int, int], tuple[int, int]]]

Runs the greedy algorithm to find pairs of cells.

Returns:

list of tuple

A list of pairs of cells, each represented as a tuple of tuples.

Raises:

ValueError

If any cell in pairs is invalid.

color_grid_game.solvers.greedy_upgraded module

class color_grid_game.solvers.greedy_upgraded.SolverGreedy_upgraded(grid: Grid, rules='original rules')

Bases: Solver

Improvement of SolverGreedy that tries all possible starting points and keeps the pairing with the minimum score.

Methods

run()	Runs the greedy algorithm from all possible starting cells and selects the best pairing.
score()	Computes the score of the list of pairs in self.pairs.

run() → list[tuple[tuple[int, int], tuple[int, int]]]

Runs the greedy algorithm from all possible starting cells and selects the best pairing.

Returns:

list of tuple

List of pairs with the lowest score.

Raises:

ValueError

If any cell in pairs is invalid.

color_grid_game.solvers.hungarian module

class color_grid_game.solvers.hungarian.SolverHungarian(grid: Grid, rules='original rules')

Bases: Solver

A solver that uses the Hungarian algorithm to find optimal pairs in a grid.

Methods

run()	Builds a bipartite cost matrix using only cells present in valid pairs.
score()	Computes the score of the list of pairs in self.pairs.

run() → list[tuple[tuple[int, int], tuple[int, int]]]

Builds a bipartite cost matrix using only cells present in valid pairs. Applies the Hungarian algorithm to find optimal pairs.

Returns:

list of tuple

A list of pairs of cells, each represented as a tuple of tuples.

Raises:

ValueError

If the cost matrix is empty or if pairs are invalid.

color_grid_game.solvers.hungarian_general module

class color_grid_game.solvers.hungarian_general.SolverHungarian_general(grid: Grid, rules='original rules')

Bases: Solver

An alternative implementation of the Hungarian algorithm solver.

Methods

run()	Builds a bipartite cost matrix using only cells present in valid pairs.
score()	Computes the score of the list of pairs in self.pairs.

run() → list[tuple[tuple[int, int], tuple[int, int]]]

Builds a bipartite cost matrix using only cells present in valid pairs. Applies the Hungarian algorithm to find optimal pairs.

Returns:

list of tuple

A list of pairs of cells, each represented as a tuple of tuples.

Raises:

ValueError

If the cost matrix is empty or if pairs are invalid.

Module contents

Solvers used in the color_grid_game package