Puzzles

Reasoning Ability – Puzzles

Advanced, MIT‑style Study Notes

1. Introduction

Puzzle solving is a cornerstone of logical reasoning. It trains:

These notes will:

1. Derive puzzle techniques from first principles.
2. Introduce rigorous theory (CSP, SAT, NP‑complete).
3. Show edge‑case handling.
4. Provide a challenging puzzle with full solution.

2. Foundations of Puzzle Reasoning

2.1 Propositional Logic

• Atoms (p, q, r, \dots) represent simple facts.
• Connectives: (\neg,\wedge,\vee,\rightarrow,\leftrightarrow).
• Truth tables give exhaustive semantics.
• Inference rules (Modus Ponens, etc.) allow valid derivations.

Example
Premises:

1. (A \rightarrow B)
2. (\neg B)
   Conclusion: (\neg A) (Contrapositive).

2.2 Set Theory & Relations

• Sets: (\mathcal{A}, \mathcal{B}, \dots).
• Relations: (R \subseteq \mathcal{A}\times \mathcal{B}).
• Properties: reflexive, symmetric, transitive → equivalence relations.
• Partitions: equivalence classes.

Application: In seating puzzles, “person (x) sits next to person (y)” is a relation on the set of people.

2.3 Combinatorics

• Counting: (n!) permutations, (\binom{n}{k}) combinations.
• Inclusion–Exclusion: counts with overlapping constraints.
• Pigeonhole Principle: guarantees repetition when items > containers.

2.4 Graph Theory Basics

• Graph (G=(V,E)).
• Vertices represent entities; edges encode relations.
• Degree, paths, cycles, coloring.
• Directed graphs for precedence constraints.

3. Types of Puzzles & Their Formal Models

4. Advanced Theoretical Tools

4.1 Constraint Satisfaction Problems (CSP)

• Variables (X_1,\dots,X_n).
• Domains (D_i).
• Constraints (C_j) (binary or higher‑arity).
• Goal: find assignment satisfying all (C_j).

4.1.1 Solving Methods

1. Backtracking – depth‑first search.
2. Arc Consistency (AC‑3) – prune impossible values.
3. Forward Checking – reduce domains ahead of time.
4. Heuristics: MRV, LCV, Degree heuristic.

4.2 SAT Solving

• Translate CSP to Conjunctive Normal Form (CNF).
• Use DPLL or CDCL algorithms.
• Variable ordering and clause learning drastically reduce search.

4.3 Graph‑Theoretic Complexity