Npc Problems: Vertex Coloring

Npc Problems: Vertex Coloring is een puzzelgame rond het probleem van graafkleuring. Je lost met de hand gemaakte puzzels op door cirkels zo in te kleuren dat verbonden cirkels verschillende kleuren hebben, met zo min mogelijk kleuren.

Het kleurprobleem

De game geeft het probleem weer met een graaf: knooppunten zijn de vertices en de lijnen die ze verbinden zijn de kanten. Je krijgt relatief kleine puzzels om op te lossen. Volgens de beschrijving is vertexkleuring een NP-volledig probleem en kunnen grote puzzels, afhankelijk van hun omvang, jaren kosten om door de computers van nu te worden opgelost. Voor grote puzzels zijn volgens de beschrijving machine learning en kunstmatige intelligentie nodig.

Toepassingen in de echte wereld

De game beschrijft verschillende toepassingen van vertexkleuring:

• Examenroosters: Stel vakken voor als vertices en verbind vakken waarvoor dezelfde studenten examen doen. Door de graaf in te kleuren, wijs je tijdslots voor examens toe. Het minimale aantal kleuren komt overeen met het minimale aantal tijdslots.
• Toewijzing van radiofrequenties: Stel zendmasten voor als vertices en verbind masten die binnen elkaars bereik staan. Verbonden masten hebben verschillende frequenties nodig. Met inkleuren bepaal je hoeveel frequenties er minimaal nodig zijn.
• Sudoku: Stel vakjes voor als vertices en verbind vakjes in dezelfde rij, kolom of hetzelfde blok.
• Kaarten inkleuren: Geef aangrenzende gebieden verschillende kleuren. Volgens de beschrijving zijn vier kleuren voldoende om elke kaart in te kleuren.

De puzzels spelen zich af in een ontspannen omgeving met neonbeelden en originele synthwavemuziek.