color_grid_game.solvers package

Submodules

color_grid_game.solvers.solver_blossom module

class color_grid_game.solvers.solver_blossom.Solver_Blossom(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

matching_dict_to_set(matching)	Converts matching dictionary format to matching set format.
max_weight_matching(G[, maxcardinality, weight])	Compute a maximum-weighted matching of the graph G.
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.

static matching_dict_to_set(matching)

Converts matching dictionary format to matching set format.

Parameters:

matchingdict

A dictionary representing the matching where keys are nodes and values are their matched pairs.

Returns:

set

A set of edges representing the matching.

Raises:

ValueError

If a self-loop is detected in the matching.

static max_weight_matching(G, maxcardinality=False, weight='weight')

Compute a maximum-weighted matching of the graph G.

Parameters:

Gnetworkx.Graph

The input graph with edge weights.

maxcardinalitybool, optional

Whether to compute a maximum cardinality matching.

weightstr, optional

The attribute key for edge weights.

Returns:

set

A set of edges representing the maximum-weighted matching.

Raises:

ValueError

If the input graph is not valid or if an error occurs during computation.

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.solver_empty module

class color_grid_game.solvers.solver_empty.Solver_Empty(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.solver_ford_fulkerson module

class color_grid_game.solvers.solver_ford_fulkerson.Solver_Ford_Fulkerson(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.
edmonds_karp(graph, even_cells, odd_cells)	Computes the maximum flow (maximum matching) in the bipartite graph using the Edmonds-Karp method.
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) → dict

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:

dict

A dictionary of parents for reconstructing the path.

classmethod edmonds_karp(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 Edmonds-Karp method.

Parameters:

graphdict

The graph represented as an adjacency list.

Returns:

list of tuple

The maximum matching as a list of pairs of cells.

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.

color_grid_game.solvers.solver_greedy module

class color_grid_game.solvers.solver_greedy.Solver_Greedy(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.solver_greedy_upgraded module

class color_grid_game.solvers.solver_greedy_upgraded.Solver_Greedy_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.solver_hungarian module

class color_grid_game.solvers.solver_hungarian.Solver_Hungarian(grid: Grid, rules='original rules')

Bases: Solver

An alternative implementation of the Hungarian algorithm solver.

Methods

hungarian_algorithm(cost)	Solve the linear sum assignment problem using the Hungarian algorithm.
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.

hungarian_algorithm(cost)

Solve the linear sum assignment problem using the Hungarian algorithm.

Parameters:

costnp.ndarray

The cost matrix of the bipartite graph.

Returns:

row_indnp.ndarray

An array of row indices giving the optimal assignment.

col_indnp.ndarray

An array of corresponding column indices giving the optimal assignment.

run()

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