¿Qué rama de las matemáticas es relevante para la comprensión de Kami 2 puzzles?

Question

Yo estoy luchando para encontrar un algoritmo para resolver de forma fiable Kami 2, rompecabezas (idealmente en Python), y me pregunto ¿qué rama de las matemáticas que tendría que empezar.

Las reglas son simples: Cada movimiento consiste en la sustitución de cualquiera contiguos región coloreada con uno de los colores disponibles (a partir de una paleta de siempre). El objetivo es que ha llenado toda la imagen con un solo color en un determinado número de movimientos (indicado en la barra de herramientas).

Supongo que este es un asunto sencillo para las personas que conocen el campo de la derecha (la teoría de grafos?) pero yo no soy uno de ellos!

Answer 1

Observar que las formas de los diferentes colores de las regiones no importa; lo que importa es que son adyacentes a cada cual. Así que usted puede quitar el problema a su esencia mediante la reducción de la disposición de las regiones a una etiqueta gráfico: Cada vértice representa una región contigua de un solo color, identificado por el color. Dos vértices están conectados por una arista si las correspondientes regiones adyacentes.

Un movimiento consiste en dos pasos:

1. Cambiar la etiqueta de un vértice.

2. Contrato de todos los vértices adyacentes con la misma etiqueta.

El objetivo es reducir la gráfica a un solo vértice.

Una obvia codiciosos estrategia es elegir el vértice que tiene la mayoría de los vértices adyacentes con la misma etiqueta, por ejemplo el tan región en la parte inferior izquierda, que tiene cuatro adyacentes rojo regiones. Es una interesante pregunta de si esta estrategia es óptima o cercana a la óptima. Esta estrategia no está aún bien definido: ¿Qué hacer si hay varios candidatos vértices? Por ejemplo, el penúltimo de la fila tiene un bronceado vértice con cuatro adyacentes rojo los vértices, y una red de vértices con cuatro adyacente tan vértices.

Answer 2

Si $c$ es el número de colores en el tablero, esta es la $c$Libre de Inundaciones Es problema. La introducción de la ponencia "árboles de expansión y la complejidad de la inundación llenando los juegos" por Meeks y Scott (2013), parece dar un buen estudio sobre lo que se sabe sobre el problema. Por ejemplo, es conocido por ser NP-Duro para el $n \times n$ cuadrícula con $c \geq 3$, y en los árboles con $c \geq 4$, y es en P al $c=2$, y también para cualquier $c$ para los caminos o ciclos.