A ticketing system with intelligent seat validation powered by a SAT solver.
Built as a Software Engineering course project. The goal was to design and implement a slice of a ticketing system where the core feature is a mechanism that prevents single-seat gaps from forming in rows. The frontend serves as a demo UI to visualize the validation logic, while the primary focus was on the backend.
The full Software Requirements Specification is included in the repository: eTicket_SRS.md (in Polish). This project implements only a subset of the features described there.
Seat validation (SAT solver)
- Single-seat gap detection in rows
- Alternative seat suggestions from current and neighboring rows
- Automatic acceptance when no better options exist
Authentication and authorization
- Registration and login with JWT
- Refresh token rotation with SHA-256 hashing
- Roles: customer, organizer, administrator
Event management
- Event listing
- Event details with sector map (seated/standing)
- Seat map per sector with occupied seat indicators
Purchase flow
- Shopping cart with timed reservation (20 minutes)
- Adding seated tickets (with SAT validation)
- Adding standing tickets (with capacity management)
- Removing items from cart
- Checkout with ticket generation
Tickets
- PDF generation with QR code
Problem: When buying tickets, customers tend to leave single empty seats (e.g. buying seats 1-2 and 4-5, leaving a gap at seat 3). These seats are really hard to sell afterwards.
Solution: Seat selection is validated as a Boolean Satisfiability Problem (SAT). Each seat in a row is a boolean variable (occupied/free). The rule is expressed as a CNF formula:
For every three adjacent seats (left, middle, right): (-left OR middle OR -right)
This clause is unsatisfied only when left=occupied, middle=free, right=occupied - exactly when a single-seat gap exists. The solver checks whether the entire formula remains satisfiable after adding the selected seats.
If validation fails, the system searches the current and neighboring rows and returns alternative seat suggestions that don't create gaps.
Implementation:
SeatGapValidator.java- generates CNF clauses from sector layout, runs validation, searches for alternativesSATSolver.java- DPLL solver with backtracking (based on Software Archetypes)Clause.java- CNF clause representation (based on Software Archetypes)
Software Archetypes: Software Archetypes - SAT
cp .env.example .env
docker compose up -d --buildFrontend: http://localhost:3000
Backend: Java 21, Spring Boot 4, Spring Security (JWT), JPA/Hibernate, MapStruct, Flyway, PostgreSQL 17
Frontend: React, Vite
Testing: JUnit
Infrastructure: Docker, GitHub Actions CI