Seat-Matrix: Greedy-Based Constraint-Aware Examination Seating Arrangement

Seat-Matrix is an algorithm-driven examination seating arrangement system designed to automate the allocation of students across examination blocks, benches, and seats.

The project emphasizes the Analysis of Algorithms (AOA) aspects of examination seating optimization rather than serving solely as a management interface. It utilizes a Greedy Method with a Priority Queue (Max Heap), sequential student allocation, matrix-based seat representation, and explicit constraint checking to generate feasible and efficient seating configurations.

Status: The core algorithm, baseline comparison approaches, test suite, sample datasets, and documentation are fully implemented. Benchmark metrics are available in docs/test-results.md.

Problem Statement

Educational institutions frequently manage examination rosters via spreadsheets, necessitating manual and time-consuming seating allocations across multiple venues. A valid arrangement must simultaneously satisfy the following parameters:

• Student strength across different classes
• Roll-number sequence integrity
• Separation by branch, division/class, and academic year/semester
• Physical constraints: Available blocks, benches per block, and seats per bench (one-seater or two-seater)
• Maximized utilization of available seating capacity

Seat-Matrix automates this process through an algorithmic framework.

Core Methodology

Student groups are treated as ordered streams based on their roll numbers. For a two-seater bench, two compatible streams are allocated in parallel to prevent adjacent seating of students from the same cohort:

Bench 01    Comp SE-B 01    |    Elec TE-A 01
Bench 02    Comp SE-B 02    |    Elec TE-A 02
Bench 03    Comp SE-B 03    |    Elec TE-A 03
Bench 04    Comp SE-B 04    |    Elec TE-A 04
...

Students remain strictly sequential within their respective classes (the Sequential Allocation Invariant) while pairings satisfy predefined hard constraints. When a block reaches maximum capacity, remaining students are allocated to the next suitable block. One-seater benches are handled independently as pairing constraints do not apply.

Algorithms & Data Structures

1. Greedy Method: At every step, the algorithm selects the most optimal local allocation given current priorities and constraints, rather than computing global optimality.
2. Priority Queue (Max Heap): Prioritizes student groups based on current remaining strength, dynamically re-ranking them after every allocation.
3. Sequential Allocation: Prevents arbitrary shuffling within a student group, enforced structurally via the GroupStream model.
4. Constraint Checking: Explicit hard constraints are evaluated prior to every pairing to prevent invalid adjacency (e.g., identical branch, division, or year-semester).
5. Matrix-Based Representation: Utilizes a Block → Bench → Seat structure to allow O(1) bidirectional lookup (Student ↔ Location) via SeatingMatrix.

System Architecture

   Student Data (Excel / CSV / PDF)
             │
             ▼
   Data Extraction & Validation  (input_parser.py)
             │
             ▼
        Group Students           (GroupStream, models.py)
             │
             ▼
      Calculate Strengths
             │
             ▼
   Priority Queue (Max Heap)     (priority_queue.py)
             │
             ▼
     Greedy Allocation           (greedy_allocator.py)
             │
             ▼
    Constraint Checking          (constraints.py)
             │
             ▼
   Seating Matrix Creation       (seating_matrix.py)
             │
             ▼
    Block Capacity Check
             │
       ┌─────┴─────┐
       │           │
    Capacity   Remaining
      Full      Students
       │           │
       └─────┬─────┘
             ▼
     Next Suitable Block
             │
             ▼
      Final Arrangement
             │
      ┌──────┼────────┐
      ▼      ▼        ▼
   Seating Search  Reports       (exporters.py, search.py, metrics.py)
    Sheet

Input Specifications

Student Data Parameters

Field	Description
Student Name	Full name of the student
Roll No.	Unique examination or student roll number
Branch	Academic branch or department
Division	Class section or division
Year	Academic year
Semester	Current academic semester
Subject	Target examination subject

Infrastructure Parameters

Field	Description
Floor	Floor designation
Block No.	Unique classroom or block identifier
Benches	Total number of available benches
Seats/Bench	Capacity per bench (1 or 2)

Supported Formats: .csv, .xlsx, .xls, and text-based .pdf. Note: Scanned or image-only PDFs are currently rejected; OCR implementation is reserved for future iterations.

Output Deliverables

• Consolidated Seating Plan: High-level summary of branch/division/semester/subject allocations with seat-number ranges and block totals.
• Detailed Block Arrangement: Granular view detailing every student's exact physical seat.
• Student Search: Query module supporting search by name, roll number, branch, or division.
• Attendance Sheet: Block-wise and student-wise logs with dedicated sign-off columns.
• Answer Sheet Mapping: Direct roll-to-seat-number mapping documentation.
• System Metrics: Statistical output detailing seat utilization percentages, empty seats, constraint conflicts, and execution time.

Export Formats: Excel (consolidated workbook), CSV, and PDF (via reportlab for tabular formatting).

Constraints & Preferences

Hard Constraints: Must be strictly satisfied for a valid arrangement. Includes seat/allocation uniqueness, block capacity limits, sequential roll ordering, and non-identical branch/division/semester assignments for bench-mates.

Soft Preferences: Utilized for deterministic tie-breaking among valid candidates. The algorithm favors the largest remaining compatible group, optimal bench utilization, minimized block transitions, and deterministic resolution via group keys.

Algorithm Analysis

Three approaches were developed operating on identical data models to facilitate empirical comparison:

Approach	Methodology	Description
1 — Sequential	Baseline	Fixed group order where the first compatible partner is permanently selected.
2 — Sort-Then-Allocate	Static	Groups are sorted once by initial strength and maintain a static order throughout execution.
3 — Greedy + Priority Queue	Primary	Adaptive re-prioritization ensures the most optimal compatible partner is selected iteratively.

Extensive time and space complexity evaluations are available in docs/complexity.md. Empirical benchmarks (docs/test-results.md) demonstrate that Approach 3 yields fewer conflicts and superior capacity utilization on unbalanced datasets, justifying the marginal increase in execution overhead.

Technology Stack

• Language: Python 3.12
• Algorithmic Concepts: Greedy Method, Priority Queue (Max Heap), Matrix/Grid Representation, Constraint Satisfaction, Complexity Analysis
• Data Processing: pandas, openpyxl, pdfplumber
• Report Generation: reportlab (PDF), openpyxl (Excel)
• User Interface: Streamlit
• Version Control: Git & GitHub

Repository Structure

seat-matrix/
│
├── README.md
├── requirements.txt
├── .gitignore
│
├── data/
│   ├── sample_students.csv
│   ├── sample_blocks.csv
│   ├── demo_sequential_students.csv
│   └── demo_sequential_blocks.csv
│
├── scripts/
│   └── benchmark.py                 # Generates benchmark data
│
├── src/
│   ├── main.py                      # Streamlit UI & Orchestration
│   ├── models.py                    # Core Data Models
│   ├── input_parser.py              # File Parsing & Validation
│   ├── priority_queue.py            # Max-Heap Implementation
│   ├── greedy_allocator.py          # Approach 3 Implementation
│   ├── baselines.py                 # Approaches 1 & 2 Implementation
│   ├── constraints.py               # Constraint Engine
│   ├── seating_matrix.py            # Grid Generation & Lookup
│   ├── search.py                    # Query Implementation
│   ├── exporters.py                 # File Generation (Excel/CSV/PDF)
│   └── metrics.py                   # Performance Telemetry
│
├── tests/
│   ├── test_constraints.py
│   ├── test_priority_queue.py
│   ├── test_allocator.py
│   └── test_edge_cases.py
│
└── docs/
    ├── algorithm.md
    ├── complexity.md
    └── test-results.md

Installation & Usage

Execute the following commands to initialize the environment, verify the test suite, and launch the application:

pip install -r requirements.txt
python3 -m unittest discover -s tests -v   # Execute test suite
python3 scripts/benchmark.py               # Reproduce benchmark metrics
streamlit run src/main.py                  # Launch user interface

Future Work

• Implementation of OCR pipelines for scanned PDF ingestion.
• Advanced soft-preference optimization (e.g., multi-step lookahead scheduling algorithms).
• Concurrent scheduling for overlapping examination sessions.
• Spatial block selection based on physical campus proximity.
• Visual rendering of classroom seating layouts.
• Integration of alternative baseline algorithms (e.g., maximum bipartite matching).

Academic Context

Seat-Matrix functions as an applied Analysis of Algorithms research project. The architectural core focuses strictly on the theoretical and empirical evaluation of the Greedy Method, Priority Queues, Constraint Satisfaction, and Sequential Allocation. UI elements, file parsers, and report generators act strictly as auxiliary components to support the core algorithmic engine. Detailed design rationales and complexity proofs are formally documented within the docs/ directory.