Puzzles

UPSC CMS – Reasoning Ability

Topic: Puzzles

(Advanced, MIT‑level treatment – first principles, rigorous reasoning, edge‑cases, and a challenging problem)

Goal: Equip the candidate with a deep, systematic approach to solving puzzles – the kind that appear in the UPSC Civil Services Exam as well as in competitive exams such as IIT–JEE, GRE, GMAT, etc.
Scope:

• Types of puzzles
• General solving framework (first principles)
• Theoretical underpinnings (combinatorics, graph theory, constraint‑satisfaction)
• Edge‑cases & pitfalls
• A challenging problem with full solution

Recommended reading:

• “Concrete Mathematics” (R. Graham, D. Knuth, O. Patashnik) – for combinatorics
• “Discrete Mathematics and Its Applications” (Kenneth H. Rosen) – for logic & graph theory
• “The Art and Craft of Problem Solving” (Paul Zeitz) – for general problem‑solving strategies

1. What is a Puzzle?

2. Categories of Puzzles

3. General Framework – First Principles

Step‑by‑Step Solver’s Algorithm

1. Read & Summarize
   • Extract entities (people, objects, positions).
   • List attributes (colors, ages, occupations).
   • Enumerate constraints (pairs, inequalities, patterns).
2. Model
   • Create a table (or matrix) and mark known values.
   • Translate constraints into logical statements (∀, ∃, ¬, ∧, ∨).
3. Inference Engine
   • Apply deductive rules (Modus Ponens, Contrapositive).
   • Use elimination (remove impossible values).
   • Implement back‑tracking if necessary (branch‑and‑bound).
4. Verification
   • Check for consistency (no contradictions).
   • Ensure uniqueness (if required).
5. Answer extraction
   • Read off the required answer(s) from the filled table.

Mathematical Formulation
Let (E = {e_1, e_2, …, e_m}) be entities,
(A = {a_1, a_2, …, a_n}) be attributes.
The puzzle is a constraint satisfaction problem (CSP) over variables (X_{ij}) where (i\in E), (j\in A).
Each constraint (C_k) is a predicate on some subset of ({X_{ij}}).
The solution is an assignment (\sigma : X_{ij} \mapsto \text{value}) satisfying all (C_k).

4. Theoretical Tools

4.1 Graph Theory

• Vertices = entities;
• Edges = “adjacent / next to” constraints.
• Coloring = assigning attributes with no two adjacent vertices sharing the same color.
• Hamiltonian paths for “visit each person exactly once” puzzles.

Edge case: Graph may be disconnected – treat each component separately.

4.2 Constraint Satisfaction & SAT

• Translate puzzle into a Boolean formula in Conjunctive Normal Form (CNF).
• Use DPLL algorithm or unit propagation to prune search space.
• Useful for binary puzzles (0–1) where each cell is a Boolean variable.

4.3 Combinatorics & Counting

• Permutation of attributes: (n!) possibilities.
• Inclusion–Exclusion for overlapping constraints.
• Pigeonhole Principle to eliminate impossible distributions.

Example: In a “no two same colors adjacent” puzzle, we can show that at least two colors are required if (n > 2) and adjacency constraints exist.

4.4 Logical Deduction Rules