The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.
The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side).
Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges
Data Structure Can be Used to Represent The Puzzle: Graph
Solution. (Unsolvable Puzzle in Computer Science)
Reason: Its application of Graph Data Structure (Idea Comes In Mind as Studied The Puzzle Carefully). so we have to traverse each bridge one & only once & returned back to source vertex if we draw the graph of this problem we found that each vertex has odd degree so its not possible to satisfy the puzzle solution. in 17's Euler already proved it unsolvable problem of computer science & said we can solve this if we have each vertex of even degree.
See This Graph Representation
Fell Free to Comment & Suggest your Approach
No comments:
Post a Comment