The old city of Königsberg, capital of East Prussia (now Kaliningrad), was built on either side of the river Pregel, with seven bridges across the river between four separate landmasses. A problem made famous by Swiss mathematician Leonard Euler is to try to find a route around the city that crosses every bridge once and only once.
To investigate this puzzle using SQL Server, we’ll model a portion of the city using two tables – one containing Polygons representing the landmasses separated by rivers, and another containing LineStrings representing the bridges across those rivers:
CREATE TABLE #islands ( islandid char(1), islandgeom geometry ); INSERT INTO #islands VALUES ('A', 'POLYGON((20.505 54.706, 20.506 54.708, 20.5077 54.7086, 20.513 54.7074, 20.514 54.7075, 20.52 54.7077, 20.52 54.71, 20.503 54.71, 20.503 54.706, 20.505 54.706))'), ('B', 'POLYGON((20.506 54.706, 20.5073 54.7083, 20.5135 54.7068, 20.5134 54.7053, 20.506 54.706))'), ('C', 'POLYGON((20.52 54.698, 20.5149 54.6999, 20.5137 54.7009, 20.51435 54.704, 20.5135 54.7046, 20.5051 54.7054, 20.503 54.7056, 20.503 54.698, 20.52 54.698))'), ('D', 'POLYGON((20.52 54.707, 20.5162 54.707, 20.514 54.707, 20.5142 54.7051, 20.515 54.704, 20.515 54.703, 20.5149 54.7008, 20.5159 54.7, 20.52 54.699, 20.52 54.707))'); CREATE TABLE #bridges( bridgeid char(1), bridgegeom geometry ); INSERT INTO #bridges VALUES (1, 'LINESTRING(20.5082 54.7092, 20.5075 54.7076)'), (2, 'LINESTRING(20.5109 54.7087, 20.5101 54.707)'), (3, 'LINESTRING(20.5148 54.708, 20.5147 54.70634)'), (4, 'LINESTRING(20.5128 54.706, 20.5147 54.7057)'), (5, 'LINESTRING(20.5069 54.70645, 20.5061 54.7048)'), (6, 'LINESTRING(20.5103 54.706, 20.5099 54.70416)'), (7, 'LINESTRING(20.5174 54.6985, 20.5187 54.7003)');
Each of the islands is lettered from A – D, and each bridge is numbered from 1 – 7, as shown in the results of the following query (I’ve applied a small buffer to the bridges only to make them easier to see in the spatial results tab):
SELECT islandid, islandgeom FROM #islands UNION ALL SELECT bridgeid, bridgegeom.STBuffer(0.0001) FROM #bridges
How, then, can we try to devise a route that crosses each bridge only once? When investigating this problem, the first conclusion reached by Euler was that the shape of the islands, and the path taken within any island, was irrelevant. All that matters is the possible connections that can be made between islands. (This conclusion, and Euler’s later work on the puzzle, led to the foundation of graph theory, in which the entities in a network can be modelled as nodes, and the relationships between those nodes defined by edges).
So, let’s create a table that maps every possible crossing between islands, the edges of the network, by using STIntersects() to determine those islands that are connected to each bridge:
CREATE TABLE #crossings( fromid char(1), viabridge char(1), toid char(1) ); INSERT INTO #crossings SELECT f.islandid AS fromid, b.bridgeid AS viabridge, t.islandid AS toid FROM #islands f JOIN #bridges b ON f.islandgeom.STIntersects(b.bridgegeom) = 1 JOIN #islands t ON b.bridgegeom.STIntersects(t.islandgeom) = 1 WHERE f.islandid != t.islandid ORDER BY f.islandid;
Having created a table with every individual bridge crossing, we can now attempt to create a continuous route across the city by navigating through that edges table using a recursive CTE. The anchor member of this query starts by looking at each individual bridge crossing from the #crossings table. Having crossed a bridge to a new island, the recursive member then joins back to the #crossings table to search for any bridges that begin on the island where the last crossing ended, in an attempt to continue the route (note the join condition – #crossings JOIN cte ON cte.toid = #crossings.fromid).
Along the way, the query concatenates the ids of all the bridges crossed into the bridgescrossed field. This field is used in a condition of the recursive member to ensure we don’t cross any bridge that’s already been included at some point in the route (WHERE bridgescrossed NOT LIKE ‘%’ + #crossings.viabridge + ‘%’).
Finally, we also concatenate both the bridge identifier and the islands visited in turn to create a nice formatted route of the journey for later examination. e.g. a journey that started at island A and went to island D via bridge 3 would be shown as A – 3 – D.
Here’s the full code listing:
WITH cte as ( SELECT #crossings.fromid, CAST(#crossings.viabridge AS varchar(32)) AS bridgescrossed, CAST(#crossings.fromid + '-' + #crossings.viabridge + '-' + #crossings.toid AS varchar(32)) as formattedroute, #crossings.toid FROM #crossings UNION ALL SELECT #crossings.fromid, CAST(cte.bridgescrossed + #crossings.viabridge AS varchar(32)) AS bridgescrossed, CAST(cte.formattedroute + '-' + #crossings.viabridge + '-' + #crossings.toid AS varchar(32)) as formattedroute, #crossings.toid FROM #crossings JOIN cte ON cte.toid = #crossings.fromid WHERE bridgescrossed NOT LIKE '%' + #crossings.viabridge + '%' ) SELECT formattedroute, len(bridgescrossed) AS numbridgescrossed FROM cte ORDER BY len(bridgescrossed) DESC;
The results show every possible route across the city that never cross the same bridge more than once, ordered to show longest routes (i.e. those that cross the most bridges) first. If any route existed that crossed every bridge, we’d expect it to be listed at the top of the results, and for the numbridgescrossed value to be 7.
However, we find that no such route exists. The longest route(s) in the resultset crosses only 6 of the 7 bridges. One such route, starting at island D and ending at island A, is as follows:
D – 7 – C – 6 – B – 4 – D – 3 – A – 2 – B – 1 – A
And that is empirical proof, using SQL Server, that no solution to this problem exists.
As for understanding why no solution exists? Consider the number of bridges connected to each island. Bear in mind that every time you arrive on an island via a bridge, you must leave that island via a different bridge. It therefore follows that, in order to follow a continuous route that crosses every bridge, every island (with the exception of the start and end island), must have an even number of bridges connected to it – a matched set of entry/exit bridge pairs. In the Konigsberg puzzle, however, Island B has 5 bridges connected to it, and Islands A, C, and D each have 3 bridges connected to them. Since, at most, only two of these islands can be the start/end points of the route, no solution is possible.