SET /Reasoning Ability

Puzzles

Non-Verbal & Puzzles · free study notes

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 → Q and P is true, then Q is 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

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.