Col (juego)

Col es un juego de lápiz y papel , específicamente un juego de colorear mapas , que consiste en sombrear áreas en un dibujo lineal según las reglas de coloración de grafos . Con cada movimiento, el grafo debe permanecer correcto (no pueden tocarse dos áreas del mismo color), y un jugador que no puede realizar un movimiento válido pierde. El juego fue descrito y analizado por John Conway , quien se lo atribuyó a Colin Vout , en su obra Sobre los números y los juegos . ^{[ 1 ]}

En el siguiente juego, el primero de los dos jugadores usa el color rojo y el segundo el azul . El último movimiento en cada imagen se muestra más brillante que las demás áreas.

El gráfico inicial:

El primer jugador puede colorear cualquiera de las áreas para comenzar. Sin embargo, la región que rodea el gráfico no se considera un área válida para este juego.

Después del primer movimiento:

El segundo jugador ahora colorea una celda blanca. Como actualmente no hay áreas azules, cualquier celda blanca es válida.

Dos movimientos dentro:

En este punto, entra en vigor el requisito de que el gráfico sea correcto, ya que debe crearse un área roja que no toque la existente:

Una vez coloreada la tercera región:

Tenga en cuenta que las áreas solo se consideran en contacto si comparten aristas, no si solo comparten vértices, por lo que este movimiento es válido.

El juego continúa, con los jugadores moviéndose alternativamente, hasta que uno de ellos 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 de que las regiones vecinas no pueden tener colores diferentes. La coloración de las regiones se explica como la asignación de campos a toros y vacas, donde los campos vecinos no pueden contener ganado del sexo opuesto, para evitar que se distraigan de su pastoreo.

Decidir el resultado en Snort es PSPACE-completo en grafos generales. ^{[ 2 ]} Esto se demuestra reduciendo el nodo partidista Kayles , que es PSPACE-completo, a un juego de Snort.

El valor de una posición Col siempre es un número o un número más un asterisco ^{[ 3 ]} Esto hace que el juego sea relativamente simple en comparación con Snort, que presenta una variedad mucho mayor de valores.

• Berlekamp, ​​Elwyn R .; John H. Conway; Richard K. Guy (1982). Winning Ways for your Mathematical Plays . Academic Press. ISBN 978-0-12-091101-1.Revisado y reimpreso como
• Berlekamp, ​​Elwyn R. (2004) [2001]. Métodos ganadores para tus juegos matemáticos (2.ª  ed.). AK Peters Ltd. ISBN 978-1-56881-130-7.
• Conway, John Horton (1976). Sobre los números y los juegos . Academic Press. ISBN 978-0-12-186350-0.Revisado y reimpreso como
• Conway, John Horton (2000). Sobre números y juegos . AK Peters Ltd. ISBN 978-1-56881-127-7.

• Juegos de Col y Snort en Google Play