Col es un juego de lápiz y papel , específicamente un juego de colorear mapas , que implica sombrear áreas en un dibujo lineal de acuerdo con las reglas de coloración de gráficos . Con cada movimiento, el gráfico debe permanecer correcto (no pueden tocarse dos áreas del mismo color), y un jugador que no pueda realizar un movimiento legal pierde. El juego fue descrito y analizado por John Conway , quien lo atribuyó a Colin Vout, en On Numbers and Games . [1]
En el siguiente juego, el primero de los dos jugadores usa rojo y el segundo usa azul . El último movimiento en cada imagen se muestra más brillante que las otras áreas.
El gráfico inicial:
El primer jugador puede colorear cualquiera de las áreas para comenzar. Sin embargo, la región alrededor del exterior del gráfico no se incluye como área para este juego.
Después del primer movimiento:
El segundo jugador ahora colorea una celda blanca. Como actualmente no hay áreas azules, se permite cualquier celda blanca.
Dos movimientos en:
En este punto entra en vigor el requisito de que el gráfico sea el adecuado, ya que se debe realizar una zona roja que no toque la existente:
Una vez coloreada la tercera región:
Tenga en cuenta que las áreas solo cuentan como en contacto si comparten aristas, no si solo comparten vértices, por lo que este movimiento es legal.
El juego continúa, los jugadores se mueven alternativamente, hasta que un jugador no puede realizar ningún movimiento. Este jugador pierde. Una posible continuación del juego es la siguiente (con cada movimiento numerado para mayor claridad):
Juego terminado:
En este resultado, el jugador azul ha perdido.
Snort, inventado por Simon P. Norton , utiliza una asignación partidista similar de dos colores, pero con la restricción anticlásica: no se permite que las regiones vecinas reciban colores diferentes. Colorear las regiones se explica como asignar campos a toros y vacas, donde los campos vecinos no pueden contener ganado del sexo opuesto, para que no se distraiga de su pasto.
Decidir el resultado en Snort es PSPACE completo en gráficos generales. [2] Esto se demuestra reduciendo el nodo partidario Kayles , que es PSPACE-completo, a un juego de Snort.
El valor de una posición Col es siempre un número o un número más una estrella [3]. Esto hace que el juego sea relativamente simple en comparación con Snort, que presenta una variedad mucho mayor de valores.