I want to solve a Sudoku puzzle in NetworkX by reducing it to a vertex coloring problem. The graph has a vertex for each cell of the Sudoku grid, and two vertices are adjacent if and only if the corresponding cells belong to the same row, column, or block. Clues are represented by additional edges in the graph, and a 9-coloring of the graph represents a solution to the puzzle.
However, it seems that all of the vertex coloring algorithms in NetworkX are heuristics, and they are not guaranteed to find a minimum vertex coloring. In my experiments, I get vertex colorings with 10 colors, even though I know that a 9-coloring exists.
How can I find a minimum vertex coloring with NetworkX?
Unfortunately, in networkx there are not exact algorithms for the chromatic number problem.
This means that you have to implement it by your own (or find some available implementations).
You might either use an exact algorithm (e.g., Lawler's Algorithm) or an ILP-based one.