Col (spel)

Col är ett penn- och papperspel , närmare bestämt ett kartfärgningsspel, som involverar skuggning av områden i en linjeritning enligt reglerna för graffärgning . Med varje drag måste grafen förbli korrekt (inga två områden av samma färg får röra), och en spelare som inte kan göra ett lagligt drag förlorar. Spelet beskrevs och analyserades av John Conway , som tillskrev det till Colin Vout, i On Numbers and Games .

Exempelspel

I följande spel använder den första av de två spelarna rött och den andra använder blått . Det sista draget i varje bild visas ljusare än de andra områdena.

Startdiagrammet:

Den första spelaren får färglägga vilket område som helst för att börja. Området runt utsidan av grafen ingår dock inte som ett område för detta spel.

Efter första draget:

Den andra spelaren färgar nu en vit cell. Eftersom inga områden för närvarande är blå är alla vita celler tillåtna.

Två drag in:

Vid denna tidpunkt träder kravet på att grafen ska vara korrekt, eftersom ett rött område måste göras som inte rör det befintliga:

När den tredje regionen är färgad:

Observera att områden bara räknas som rörande om de delar kanter, inte om de bara delar hörn, så detta drag är lagligt.

Spelet fortsätter, spelare rör sig omväxlande, tills en spelare inte kan göra ett drag. Den här spelaren förlorar. En möjlig fortsättning på spelet är som följer (med varje drag numrerat för tydlighetens skull):

Spel över:

I det här resultatet har den blå spelaren förlorat.

Fnysa

Snort, uppfunnet av Simon P. Norton , använder en liknande partisan tilldelning av två färger, men med den antiklassiska begränsningen: angränsande regioner får inte ges olika färger. Att färga områdena förklaras som att tilldela fält till tjurar och kor, där närliggande fält inte får innehålla nötkreatur av det motsatta könet, så att de inte distraheras från sitt bete.

Att bestämma resultatet i Snort är PSPACE-komplett på allmänna grafer. Detta bevisas genom att reducera partizan-noden Kayles , som är PSPACE-komplett, till ett spel Snort.

Analys

Värdet på en Col-position är alltid antingen en siffra eller en siffra plusstjärna. Detta gör spelet relativt enkelt jämfört med Snort, som har en mycket större variation av värden.

Berlekamp, Elwyn R. ; John H. Conway; Richard K. Guy (1982). Vinnande sätt för dina matematiska pjäser . Akademisk press. ISBN 978-0-12-091101-1 . Reviderad och omtryckt som
Berlekamp, Elwyn R. (2004) [2001]. Vinnande sätt för dina matematiska pjäser (2:a upplagan). AK Peters Ltd. ISBN 978-1-56881-130-7 .
Conway, John Horton (1976). Om siffror och spel . Akademisk press. ISBN 978-0-12-186350-0 . Reviderad och omtryckt som
Conway, John Horton (2000). Om siffror och spel . AK Peters Ltd. ISBN 978-1-56881-127-7 .

externa länkar

[1] Col and Snort-spel på Google Play