Advanced Study Notes: Puzzles – The Art & Science of Structured Reasoning
Program: SET
Subject: Reasoning Ability
Topic: Puzzles
These notes are written for a university‑level course (MIT‑style) that treats puzzles as a formalized reasoning discipline.
They assume familiarity with discrete mathematics, basic logic, and algorithmic thinking.
1. What is a Puzzle?
| Definition | Key Features |
|---|---|
| A constrained problem that invites structured reasoning to reach a unique or optimal solution. | • Well‑defined state space. • Finite but potentially large. |
A formal system: P = (S, I, A, C, G) where: |
• S – set of all possible states.• I ⊆ S – initial states.• A – allowed actions (transitions).• C ⊆ S × S – constraints (legal moves).• G ⊆ S – goal states. |
| A human‑centric challenge: it must be solvable by manual reasoning (or with minimal computation). | • Requires interpretation of language, symbols, or spatial cues. |
First Principles:
- Information Theory: puzzles maximize information gain per inference.
- Computational Complexity: many puzzles map to NP‑hard problems; human solvers exploit heuristics rather than brute force.
- Logic Theory: puzzles are instances of constraint satisfaction problems (CSPs).
2. Taxonomy of Puzzles
| Category | Typical Examples | Formal Model | Common Reasoning Techniques |
|---|---|---|---|
| Deductive Logic Puzzles | Zebra puzzle, Einstein riddle | CSP with binary constraints | Truth tables, elimination, inference chains |
| Combinatorial / Counting Puzzles | Sudoku, Kakuro | CSP with arithmetic constraints | Backtracking, constraint propagation, counting arguments |
| Spatial / Geometric Puzzles | Tangram, Jigsaw | Graph/plane tiling | Graph embeddings, planar geometry, symmetry analysis |
| Game‑like Strategy Puzzles | Chess endgames, Nim variants | Game trees | Minimax, game‑theoretic equilibria, strategy stealing |
| Word/Language Puzzles | Cryptograms, crosswords | Constraint satisfaction over alphabets | Pattern matching, frequency analysis |
| Algorithmic / Coding Puzzles | Programming contests, CodeGolf | Turing‑complete programs | Dynamic programming, greedy algorithms |
Edge‑Case Puzzles
- Ambiguity: e.g., “A man sees a woman in the mirror” – requires careful linguistic parsing.
- Trick Puzzles: “The answer is in the question” – rely on meta‑information.
- Unsolvable/Over‑Constrained: Demonstrates the importance of feasibility checks.
3. Core Reasoning Principles
3.1 Deduction
- From general to specific.
- Formal: If
P → QandPis true, thenQis true. - Example: In the Zebra puzzle, if the German owns the fish, and the German lives in the green house, then the fish lives in the green house.
3.2 Induction
- From specific to general.
- More common in combinatorial reasoning: noticing a pattern across cases.
- Example: Counting the number of ways to fill a 9×9 Sudoku grid that satisfies row/column/box constraints.
3.3 Abduction
- Inference to the best explanation.
- Useful when clues are incomplete.
- Example: In a missing‑person puzzle, you abduct that the protagonist must have left the house at a certain time given the available evidence.
3.4 Contradiction (Reductio ad Absurdum)
- Assume a candidate solution; if it leads to a violation of a constraint, discard it.
- Example: In a logic grid puzzle, assume “The Japanese owns the dog”; if it conflicts with “The Japanese lives in the third house”, the assumption is false.
3.5 Symmetry & Invariance
- Identify transformations that preserve constraints to reduce search space.
- Example: Rotations of a Rubik’s Cube that preserve the solved state.
3.6 Constraint Propagation
- Propagate implications of a constraint to reduce domain sizes.
- Formal: For CSP, use Arc Consistency (AC‑3) or Path Consistency (PC‑2).
- Example: In Sudoku, once a digit is placed in a cell, eliminate that digit from the same row, column, and box.
4. Advanced Theoretical Foundations
| Theory | Relevance to Puzzles | Key Result |
|---|---|---|
| Graph Theory | Many puzzles become graph coloring / path finding problems. | Brooks’ Theorem; Chromatic number bounds. |
| Combinatorial Design | Sudoku is a Latin square; Sudoku constraints correspond to orthogonal arrays. | Euler's 36 officers problem; existence of orthogonal Latin squares. |
| Computational Complexity | Puzzle solvability often NP‑hard. | Sudoku solving is NP‑complete; Graph coloring is NP‑complete. |
| Algorithmic Game Theory | Game‑like puzzles model strategic interactions. | Minimax theorem; strategy stealing argument. |
| Information Theory | Optimal solving often maximizes information per step. | Minimum entropy coding for puzzle clues. |
| Logic & Model Theory | Puzzles |