Compendium

Here is the list of games and puzzles that are currently in our index.
Is your favorite game missing? Are you aware of a new complexity result for one of the listed games? You are welcome add or edit the listed games by following the instructions on this page.
• 15-puzzle ($n^2-1$ puzzle)
$n^2-1$ numbered tiles can be slid in a $n \times n$ board with the goal of arranging them in increasing order.
• Amazons
Two players move amazons on a square board. After moving, an amazon shoots an arrow that blocks movement. The last player to move wins.
• Bejeweled
A player swaps adjacent items in a $n \times m$ grid in order to form as many matches of three as possible.
• Boulder Dash
A single-player game in which the character digs through a rectangular grid to find diamonds within a time limit, while avoiding various dangers.
• Candy Crush
A variant of Bejeweled.
• Clickomania (SameGame)
A single player game in which the player removes groups of tiles of the same color in a rectangular board.
• Deflektor
A single-player game where the player orients mirrors to direct a laser to a target.
• Hanabi
A cooperative card game in which players can see others' cards but not their own. Players exchange hints with the goal of playing the cards in a specific order.
• Hanano
A puzzle game involving colored stones and flowers. The player moves and swaps stones. Flowers spread to adjacent stones of the same color. The goal is to bloom flowers on all the stones.
• Hashiwokakero (Hashi, Bridges)
A single player game in which the player must build orthogonal bridges to connect islands.
• Hiroimono
A single player game in which the player moves on a rectangular grid picking up stones as they are encountered, possibly changing direction at the stones' locations.
• Jelly No Puzzle
A single player side-view game in which colored jellies can be moved horizontally and are affected by gravity. When two jellies of the same color touch they merge into a single jelly. The goal is to merge all jellies of each color.
• Kingdomino
A multiplayer game in which colored dominoes are tiled in a square square board to maximize a weighted sum of the monochromatic regions' sizes.
• Lemmings
A puzzle game where the player guides a sequence of characters to safety by assigning them skills.
• Light Up (Akari)
A single player game in which the player places light bulbs in rectangular black and white grid to light up all white cells.
• Memory (Concentration)
The Memory Solitaire game consists in flipping pairs of cards laid face down and finding matches.
• Minesweeper
A puzzle in which the player needs to identify the location hidden mines in a rectangular board by using numeric clues.
A single player game in which the player connects pairs of points in a rectangular grid with paths that traverse all the grid cells and avoid unnecessary turns.
• Peg Duotaire
Given an initial configuration of pegs on a board, two players alternate in moving a peg as in Peg Solitaire, and the winner is the last player to move.
• Peg Solitaire
Given an initial and a final configuration of pegs on a board, find a sequence of peg-solitaire moves that transforms the initial configuration into the final one.
• Polyomino Packing
Given a collection of polyominoes, pack them into a target shape.
• Reversi (Othello)
Two players take turn placing reversible disks on a square board. Moves reverse one or more of the opponent's disks.
• Shannon Switching Game on Vertices (Hex)
Blue and Red alternate in coloring the vertices of a graph $G$. Blue wants to connect two distinguished vertices $s,t$ of $G$ with a blue path. Red wants to select a $s$-$t$ vertex-cut.
• Shannon Switching Game (Gale, Bridg-it)
Blue and Red alternate in coloring the edges of a graph $G$. Blue wants to connect two distinguished vertices $s,t$ of $G$ with a blue path. Red wants to select a $s$-$t$ edge-cut.
• Simultaneous Maze Solving
Find a short sequence of moves that solves several mazes at once.
• Skyscrapers (Building puzzle)
A single player game in which the player must arrange skyscrapers on a square grid so that only certain number of skyscrapers are visible from each row/column, and the skyscrapers' heights form a Latin square.
• Solitaire Army
Given a region of a board and a target position inside that region, find a configuration of pegs outside the region and a sequence of moves that allows some peg to reach the target position.
• Spiral Galaxies
A puzzle in which the player tiles a grid with polyominos with 180° rotational symmetry about given centers.
• Tents
A single player game in which trees are arranged in a grid and the player places pairwise non-adjacent tents next to them so that trees and tents can be matched.
• Tetris
A single player game in which the player packs tetrominoes in a rectangular board.
• Trainyard
A puzzle game in which the player has to lay down tracks to get colored trains from their departure stations to a suitable destination stations.
• TwixT
Two players take turns placing colored pegs on a rectangular board. Pegs of the same player that are a knight's move away from each other can be linked together. The goal is to connect two opposing sides of the board with a chain of links.
• Two Dots
Collect colored dots arranged in a rectangular board by drawing monochromatic paths.
• Zig-Zag Numberlink (Flow Free)
A single player game in which the player connects pairs of points in a rectangular grid with paths traversing all the grid cells.
@misc{cog:index,
author = "{CoG contributors}",
title  = "{Complexity of Games Compendium}",
year   = "2022",
url    = "https://www.isnphard.com/i/",
note   = "[Online; accessed 2022-06-02]"
}