In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an king's graph is a king's graph of an chessboard.
For a king's graph the total number of vertices is simply .
For a king's graph the total number of vertices is simply and the total number of edges is . Additionally, the number of edges for various is identified as A002943 in the On-Line Encyclopedia of Integer Sequences.
Neighbourhood in the king's graph corresponds to the Moore neighborhood for cellular automata.
The logic puzzle game Hidato is based on King's graph.
Famous quotes containing the words king and/or graph:
“Our king went forth to Normandy,
With grace and might of chivalry,
The God for him wrought marvellously,
Wherefore England may call and cry
Deo gratias, Deo gratias Anglia
Redde pro victoria.”
—Unknown. The Agincourt Carol (l. 1–6)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)