Some Important Computer Science Puzzles

May 2019

This note gives a list of theoretical problems that are important to computer science. It is meant to be regularly updated with the various finds dug out from some bibliographical excavations.

Knight's tour Instance of the Hamiltonian cycle finding problem with a simple heuristic (Warnsdorff's rule)
N-Queens Simple example to illustrate backtracking
Stable marriages Reference problem when considering offer/demand systems
Post's correspondance problem Often used to prove the undecidabilty of some decision problem
Wang tiles Useful for procedural generation: with as few as 11 basic tile patterns, a plane can be tiled aperiodically
Rule 110 Similar to Wang tiles, to the difference that it displays a high amount of near similar patterns
Equational logic Convenient for a logical (or computational) introduction to abstract algebras
Unbounded nondeterminism Well-known problem when considering concurrent systems