Npc Problems: Vertex Coloring

Npc Problems: Vertex Coloring is a puzzle game built around the graph vertex coloring problem. You solve handcrafted instances by coloring circles so that linked circles have different colors, using the minimum number of colors.

The coloring problem

The game represents the problem with a graph: nodes are vertices, and lines connecting them are edges. It presents relatively small instances for you to solve. The description notes that vertex coloring is an NP-complete problem and that large instances can take today's computers years to solve, depending on their size; it says machine learning and artificial intelligence are needed to solve large instances.

Real-world applications

The game describes several uses of vertex coloring:

• Exam scheduling: Represent subjects as vertices and connect subjects that share students. Coloring the graph assigns exam time slots, with the minimum number of colors corresponding to the minimum number of slots.
• Radio frequency assignment: Represent towers as vertices and connect towers within range. Connected towers need different frequencies, and coloring helps determine the minimum number needed.
• Sudoku: Represent cells as vertices, connecting cells in the same row, column or block.
• Map coloring: Color adjacent regions differently; the description states that four colors are sufficient to color any map.

The puzzles take place in a relaxing environment with neon graphics and original synthwave music.