SQL Spatial Puzzle #3: The Seven Bridges of Königsberg

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.

image

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

image

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.

image

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.

About these ads
This entry was posted in Spatial, SQL Server and tagged , , . Bookmark the permalink.

2 Responses to SQL Spatial Puzzle #3: The Seven Bridges of Königsberg

  1. Davos says:

    Nice post.

    It appears (according to google maps) that there are now only 4 bridges, so the problem is now solvable :p

    How did you determine those coordinates for the landmass polygons? I realise it’s a rough map to illustrate the point of the challenge, but I’m hoping that part didn’t take you a long time.

    • alastaira says:

      Thanks! Ah yes, the “brute force” solution to the problem – just destroy a couple of the bridges…
      To answer your question, I used a little javascript code to draw the landmasses on Bing Maps and then retrieved the coordinates of each vertex to create the WKT of the polygons, so it didn’t take long. I must get round to copying up my drawing code, so that’ll be another post!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s