Earlier, I wrote a blog post, SQL SERVER – The Two Doors, Two Guards Puzzle, and I received lots of appreciation for it. If you have not yet checked that blog post out, it is a fun post to read. Today we are going to see another such puzzle – The Flight Connection Puzzle.
Suppose you have a flight table with columns FlightID, Origin, Destination, and DepartureTime. Each entry in the table represents a direct flight from an origin city to a destination city. The challenge is to write a SQL query that, given an origin city and a destination city, finds all possible routes between the origin and the destination, with any number of connecting flights. Assume that a connecting flight must depart at least one hour after the previous flight arrives.
Setting Up the Scenario
Let’s first set the stage by creating our Flights
 table and populating it with some data:
CREATE TABLE Flights ( FlightID INT PRIMARY KEY, Origin VARCHAR(255), Destination VARCHAR(255), DepartureTime DATETIME, ArrivalTime DATETIME ); INSERT INTO Flights VALUES (1, 'New York', 'Chicago', '2023-08-01 08:00:00', '2023-08-01 10:00:00'); INSERT INTO Flights VALUES (2, 'Chicago', 'Los Angeles', '2023-08-01 12:00:00', '2023-08-01 14:00:00'); INSERT INTO Flights VALUES (3, 'Los Angeles', 'San Francisco', '2023-08-01 16:00:00', '2023-08-01 18:00:00'); INSERT INTO Flights VALUES (4, 'New York', 'San Francisco', '2023-08-01 09:00:00', '2023-08-01 12:00:00'); INSERT INTO Flights VALUES (5, 'Chicago', 'San Francisco', '2023-08-01 15:00:00', '2023-08-01 17:00:00');
The Solution
To solve this puzzle, we’ll use a feature of SQL Server called recursive Common Table Expressions (CTEs). Recursive CTEs are a powerful tool that can solve problems involving repeated or looped operations, such as traversing hierarchies or – in our case – finding all possible paths between two points.
Here’s the solution:
DECLARE @origin VARCHAR(255) = 'New York'; DECLARE @destination VARCHAR(255) = 'San Francisco'; WITH Route AS ( SELECT FlightID, Origin, Destination, DepartureTime, ArrivalTime, CAST(Origin + ' -> ' + Destination AS VARCHAR(MAX)) AS Path FROM Flights WHERE Origin = @origin UNION ALL SELECT f.FlightID, f.Origin, f.Destination, f.DepartureTime, f.ArrivalTime, CAST(r.Path + ' -> ' + f.Destination AS VARCHAR(MAX)) AS Path FROM Flights f JOIN Route r ON f.Origin = r.Destination AND f.DepartureTime > DATEADD(hour, 1, r.ArrivalTime) ) SELECT Path FROM Route WHERE Destination = @destination;
This query constructs all possible paths from the origin city to the destination city that meet the condition of having at least one hour between connecting flights.
That’s it for today’s puzzle. Remember, SQL Server is not just a tool for managing data. It’s also a powerful engine for solving complex problems. So keep practicing and pushing the boundaries of what you can do with SQL. You can always connect with me on YouTube.
Reference:Â Pinal Dave (https://blog.sqlauthority.com)
5 Comments. Leave new
The only rhing I would change is use datetimeoffset due to crossing timezones
Should this be using “>=” instead of just “>”?
AND f.DepartureTime > DATEADD(hour, 1, r.ArrivalTime)
So I was playing with a puzzle trying to find the shortest distance one would have to travel to go to every capital in the contiguous 48 states. Would this also be a SQL based solution for that?
That would be super interesting solution. However, this requires the distance between all the cities and may be we can find one such solution easily. Other thing is that we do not have details about how to roads are connected so it is difficult to come up with the real practical answer.
Is recurcive CTE possible in sqlite?