Col es un juego de lápiz y papel , específicamente un juego de colorear mapas , que implica el sombreado de áreas en un dibujo de líneas de acuerdo con las reglas de colorear Graph . Con cada movimiento, el gráfico debe permanecer correcto (no se pueden tocar dos áreas del mismo color), y un jugador que no puede 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]
Juego de ejemplo
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 correcto, ya que se debe realizar una zona roja que no toque la existente:
Una vez que se colorea la tercera región:
Tenga en cuenta que las áreas solo cuentan como tocantes si comparten bordes, 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 hacer un 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.
Resoplido
Snort, inventado por Simon P. Norton , utiliza una asignación partidista similar de dos colores, pero con la restricción anticlásica: las regiones vecinas no pueden recibir 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 que no se distraigan de su pastoreo.
Decidir el resultado en Snort es PSPACE completo en gráficos generales. [2] Esto se demuestra reduciendo el nodo partizan Kayles , que es PSPACE completo, a un juego de Snort.
Análisis
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.
Referencias
- Berlekamp, Elwyn R .; John H. Conway; Richard K. Guy (1982). Formas ganadoras para tus juegos matemáticos . Prensa académica. ISBN 978-0-12-091101-1. Revisado y reimpreso como
- Berlekamp, Elwyn R. (2004) [2001]. Formas ganadoras para tus juegos matemáticos (2ª ed.). AK Peters Ltd. ISBN 978-1-56881-130-7.
- Conway, John Horton (1976). Sobre números y juegos . Prensa académica. 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.
- ^ Sobre números y juegos : 1
- ^ Demaine, Erik; Hearn, Robert (2001). "Jugar juegos con algoritmos: teoría de juegos combinatorios algorítmicos". arXiv : cs / 0106019v2 .
- ^ Maneras ganadoras : 2
Enlaces externos
- [1] Juegos de Col y Snort en Google Play
