DILR – Puzzles
Program: CAT (MBA)
Subject: Data Interpretation & Logical Reasoning (DILR)
Topic: Puzzles
Goal of this module – Equip you with a first‑principles understanding of logic puzzles, and the mathematical tools to analyze, solve, and even prove properties about them.
Audience – Students who want a rigorous, MIT‑style treatment that goes beyond “guess‑and‑check” to formal reasoning, algorithmic insight, and deeper theory.
1. Why Puzzles in DILR?
| Aspect | Why it matters in CAT |
|---|---|
| Logical deduction | The CAT “Logical Reasoning” section often uses puzzle‑style problems (grid puzzles, seating arrangements, scheduling). |
| Pattern recognition | Recognizing hidden structure speeds up solving and reduces errors. |
| Time management | Knowing the structure of a puzzle lets you prune impossible branches quickly. |
| Complexity awareness | Some puzzles are NP‑hard; you can decide when a brute‑force approach is feasible. |
2. Mathematical Foundations
2.1 Basic Concepts
| Concept | Definition | Example |
|---|---|---|
| Set | A collection of distinct objects. | {A, B, C} |
| Permutation | An arrangement of items. | 3! = 6 ways to arrange 3 persons. |
| Combination | A selection of items without regard to order. | C(5,2)=10 ways to pick 2 cars from 5. |
| Graph | A set of vertices connected by edges. | People as vertices; “seated next to” as edges. |
| Constraint Satisfaction Problem (CSP) | Variables, domains, constraints. | Each person’s seat is a variable with domain {1,…,6}. Constraints encode “not next to”. |
2.2 Formal Language
- Propositional Logic:
p ∧ q(both true),¬p(not p). - First‑order Logic: Quantifiers
∀,∃plus predicates (e.g.,NextTo(x, y)). - SAT: Boolean satisfiability problem.
- CP: Constraint Programming – specialized for puzzles.
3. Types of Puzzles in DILR
| Category | Typical examples | Key reasoning tools |
|---|---|---|
| Grid/Logic “Zebra” puzzles | 5 houses, 5 colors, 5 pets. | Bipartite matching, elimination. |
| Seating/Arrangement puzzles | 6 people around a table, constraints on adjacency. | Circular permutations, graph coloring. |
| Time‑table puzzles | 4 classes, 3 rooms, constraints on times. | Scheduling, bipartite matching. |
| Number puzzles | 3x3 magic square, Sudoku. | Algebra, combinatorics, Latin squares. |
| Word/Pattern puzzles | Cross‑word type, letter constraints. | Combinatorial design, graph theory. |
4. Formalizing a Puzzle as a CSP
- Variables: Each unknown quantity.
V = {v₁, v₂, …, vₙ} - Domains: Possible values for each variable.
D(vᵢ) = {d₁, …, d_k} - Constraints: Relations that must hold.
C = {c₁, …, c_m}
4.1 Example: 5‑person seating puzzle
| Variable | Domain |
|---|---|
Seat(John) |
{1, 2, 3, 4, 5} |
Seat(Mary) |
{1, 2, 3, 4, 5} |
| … | … |
Constraint: Seat(John) ≠ Seat(Mary) (no two people same seat).
Constraint: |Seat(John) - Seat(Mary)| ≠ 1 (not adjacent).
5. Algorithmic Approaches
| Approach | When it shines | Complexity |
|---|---|---|
| Brute force | Small domain (≤ 7). | O(n!) |
| Backtracking | General CSP, pruning via forward checking. | Exponential worst‑case, linear average for many puzzles. |
| Constraint propagation (AC‑3, MAC) | Tight constraints. | O(n³) in worst case. |
| Graph coloring | Seating / adjacency constraints. | NP‑complete in general. |
| Reduction to SAT | Many puzzles can be encoded as Boolean formulas. | Modern SAT solvers solve millions of variables quickly. |
| Dynamic programming | Problems with optimal sub‑structure (e.g., certain scheduling). | Exponential or polynomial depending on state space. |
5.1 Backtracking + Forward Checking Example
- Pick variable with smallest domain (MRV heuristic).
- Assign a value.
- Propagate constraints (remove incompatible values from neighbors).
- If any domain becomes empty → backtrack.
- Repeat until all variables assigned