Npc Problems: Vertex Coloring

Npc Problems: Vertex Coloring es un juego de puzles basado en el problema del coloreado de vértices de un grafo. Resuelve niveles diseñados a mano coloreando círculos de forma que los círculos conectados tengan colores distintos, usando el menor número de colores posible.

El problema del coloreado

El juego representa el problema mediante un grafo: los nodos son vértices y las líneas que los conectan son aristas. Te propone casos relativamente pequeños para que los resuelvas. La descripción señala que el coloreado de vértices es un problema NP-completo y que, según su tamaño, los ordenadores actuales pueden tardar años en resolver casos grandes; también afirma que se necesitan el aprendizaje automático y la inteligencia artificial para resolverlos.

Aplicaciones en el mundo real

El juego describe varios usos del coloreado de vértices:

• Organización de exámenes: Representa las asignaturas como vértices y conecta las que comparten estudiantes. Colorear el grafo asigna franjas horarias a los exámenes; el número mínimo de colores se corresponde con el número mínimo de franjas.
• Asignación de frecuencias de radio: Representa las torres como vértices y conecta las que están dentro del alcance. Las torres conectadas necesitan frecuencias distintas, y colorear el grafo ayuda a determinar el número mínimo necesario.
• Sudoku: Representa las casillas como vértices y conecta las que están en la misma fila, columna o bloque.
• Coloreado de mapas: Colorea de forma distinta las regiones adyacentes; la descripción afirma que bastan cuatro colores para colorear cualquier mapa.

Los puzles se desarrollan en un ambiente relajante, con gráficos de neón y música synthwave original.