Col is a

pencil and paper game Paper-and-pencil games or paper-and-pen games (or some variation on those terms) are games that can be played solely with paper and pencils (or other writing implements), usually without erasing. They may be played to pass the time, as icebre ...

, specifically a map-coloring game, involving the shading of areas in a line drawing according to the rules of

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

. With each move, the graph must remain

proper Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...

(no two areas of the same colour may touch), and a player who cannot make a legal move loses. The game was described and analysed by

John Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...

, who attributed it to

Colin Vout Colin may refer to: * Colin (given name) * Colin (surname) * ''Colin'' (film), a 2008 Cannes film festival zombie movie * Colin (horse) (1905–1932), thoroughbred racehorse * Colin (humpback whale), a humpback whale calf abandoned north of Sydney, ...

, in ''

On Numbers and Games ''On Numbers and Games'' is a mathematics book by John Horton Conway first published in 1976. The book is written by a pre-eminent mathematician, and is directed at other mathematicians. The material is, however, developed in a playful and unpre ...

''.

Example game

In the following game, the first of the two players is using

red Red is the color at the long wavelength end of the visible spectrum of light, next to orange and opposite violet. It has a dominant wavelength of approximately 625–740 nanometres. It is a primary color in the RGB color model and a secondar ...

, and the second is using

blue Blue is one of the three primary colours in the RYB colour model (traditional colour theory), as well as in the RGB (additive) colour model. It lies between violet and cyan on the spectrum of visible light. The eye perceives blue when obs ...

. The last move in each image is shown brighter than the other areas. The starting graph:
image:ColAndSnortGraph blank.png The first player may colour any of the areas to begin. However, the region around the outside of the graph is not included as an area for this game. After the first move:
image:ColAndSnortGraph C1.png The second player now colours a white cell. As no areas are currently blue, any white cell is allowed. Two moves in:
image:ColAndSnortGraph C2.png At this point, the requirement that the graph be proper comes into effect, as a red area must be made which does not touch the existing one: Once the third region is coloured:
image:ColAndSnortGraph C3.png Note that areas only count as touching if they share edges, not if they only share vertices, so this move is legal. The game continues, players moving alternately, until one player cannot make a move. This player loses. A possible continuation of the game is as follows (with each move numbered for clarity): Game over:
image:ColAndSnortGraph C end.png In this outcome, the blue player has lost.

Snort

Snort, invented by Simon P. Norton, uses a similar partisan assignment of two colors, but with the anticlassical constraint: neighboring regions are not allowed to be given different colors. Coloring the regions is explained as assigning fields to bulls and cows, where neighboring fields may not contain cattle of the opposite sex, lest they be distracted from their grazing. Deciding the outcome in Snort is

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...

on general graphs. This is proven by reducing partizan node Kayles, which is PSPACE-complete, to a game of Snort.

Analysis

The value of a Col position is always either a number or a number plus

star A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...

Winning Ways: 2 This makes the game relatively simple compared with Snort, which features a much greater variety of values.

References

* Revised and reprinted as * * Revised and reprinted as * {{reflist

External links

Col and Snort games on Google Play Paper-and-pencil games Combinatorial game theory Graph coloring