A combinatorial game is a game of no chance with no hidden information, where players alternate moves on a shared position; a puzzle is its one-player counterpart. This concept covers how such games are classified by computational complexity: which board positions can be decided in polynomial time, which are NP-complete (typically one-player puzzles where a solution is a short certificate), which are PSPACE-complete (typically two-player games of polynomially bounded length, reduced from Quantified Boolean Formulas), and which are EXPTIME-complete (two-player games whose play can last exponentially long, such as generalized chess, checkers and Go). It also covers the two analytic frameworks used to obtain these results: combinatorial game theory proper, where a sum of independent games is analyzed via surreal numbers and Sprague-Grundy values, and Constraint Logic, a family of edge-reversal games on constraint graphs whose zero-, one-, two- and team-player variants give a uniform source problem for hardness reductions across bounded, unbounded and imperfect-information settings. Students learn to place a specific game or puzzle in this landscape by identifying its player count, whether play length is bounded, and whether information is perfect, and then reducing an appropriate canonical hard problem to it.
A combinatorial game is a game of perfect information with no chance and no hidden state: two players alternating moves (Chess, Go, Konane), one player solving a puzzle (Rush Hour, Sokoban, Sudoku), …