Npc Problems: Vertex Coloring

Npc Problems: Vertex Coloring é um jogo de quebra-cabeças baseado no problema de coloração dos vértices de um grafo. Resolva desafios feitos à mão colorindo círculos para que os círculos conectados tenham cores diferentes, usando o menor número possível de cores.

O problema da coloração

O jogo representa o problema por meio de um grafo: os nós são vértices, e as linhas que os conectam são arestas. Ele apresenta desafios relativamente pequenos para você resolver. A descrição observa que a coloração de vértices é um problema NP-completo e que, dependendo do tamanho, computadores atuais podem levar anos para resolver instâncias grandes; também afirma que o aprendizado de máquina e a inteligência artificial são necessários para resolvê-las.

Aplicações no mundo real

O jogo descreve vários usos da coloração de vértices:

• Programação de provas: Represente as matérias como vértices e conecte aquelas que têm alunos em comum. A coloração do grafo atribui horários às provas, e o número mínimo de cores corresponde ao número mínimo de horários.
• Atribuição de frequências de rádio: Represente as torres como vértices e conecte as que estão dentro do alcance umas das outras. Torres conectadas precisam de frequências diferentes, e a coloração ajuda a determinar o número mínimo necessário.
• Sudoku: Represente as células como vértices e conecte aquelas que estão na mesma linha, coluna ou bloco.
• Coloração de mapas: Pinte regiões adjacentes com cores diferentes; a descrição afirma que quatro cores são suficientes para colorir qualquer mapa.

Os quebra-cabeças se passam em um ambiente relaxante, com gráficos neon e música synthwave original.