Npc Problems: Vertex Coloring

Npc Problems: Vertex Coloring ist ein Puzzlespiel rund um das Problem der Knotenfärbung in Graphen. Du löst handgefertigte Aufgaben, indem du Kreise so einfärbst, dass verbundene Kreise unterschiedliche Farben haben – und dabei so wenige Farben wie möglich verwendest.

Das Färbungsproblem

Das Spiel stellt das Problem mithilfe eines Graphen dar: Knoten entsprechen den Ecken, und die Linien zwischen ihnen sind Kanten. Es präsentiert relativ kleine Aufgaben, die du lösen kannst. Laut Beschreibung ist die Knotenfärbung ein NP-vollständiges Problem, und große Aufgaben können je nach Umfang Jahre dauern, bis sie von heutigen Computern gelöst werden. Für große Aufgaben seien maschinelles Lernen und künstliche Intelligenz erforderlich.

Anwendungen in der realen Welt

Das Spiel beschreibt mehrere Einsatzmöglichkeiten der Knotenfärbung:

• Prüfungsplanung: Fächer werden als Knoten dargestellt; Fächer mit gemeinsamen Schülern werden miteinander verbunden. Durch das Färben des Graphen werden Prüfungszeitfenster zugewiesen. Die minimale Anzahl an Farben entspricht dabei der minimalen Anzahl an Zeitfenstern.
• Funkfrequenzzuweisung: Sendemasten werden als Knoten dargestellt und miteinander verbunden, wenn sie sich in Reichweite befinden. Verbundene Sendemasten benötigen unterschiedliche Frequenzen. Durch das Färben lässt sich die minimale Anzahl benötigter Frequenzen ermitteln.
• Sudoku: Zellen werden als Knoten dargestellt. Zellen in derselben Zeile, Spalte oder demselben Block werden miteinander verbunden.
• Kartenfärbung: Benachbarte Gebiete werden unterschiedlich eingefärbt. Laut Beschreibung reichen vier Farben aus, um jede Karte einzufärben.

Die Rätsel spielen in einer entspannten Umgebung mit Neon-Grafik und originaler Synthwave-Musik.