Write Code In Java Konigsberg Bridge Puzzle Objective: This problem is widely ac

Question

Write Code In Java

Konigsberg Bridge Puzzle

Objective:

This problem is widely accepted as the problem that gave birth to graph theory, and was solved by Swiss mathematician Leonhard Euler (1707-1783). The problem states is it possible in one single walk could a person traverse all seven bridges in Konigsberg exactly once and return to the starting point. The graphic below shows how the seven bridges are configured. Solve the problem by creating a graph that models the environment, and determine if this can be done.

Explanation / Answer

public class LegalGraph{ public List quadrants = new List(); public LegalGraph(){ //Create all 6 quadrants and put them in the hash Quadrant quad0 = new Quadrant(0); Quadrant quad1 = new Quadrant(1); Quadrant quad2 = new Quadrant(2); Quadrant quad3 = new Quadrant(3); Quadrant quad4 = new Quadrant(4); Quadrant quad5 = new Quadrant(5); quadrants.Add(quad0); quadrants.Add(quad1); quadrants.Add(quad2); quadrants.Add(quad3); quadrants.Add(quad4); quadrants.Add(quad5); //Foreach quadrant we will now create the relationship Bridge bridge = null; bridge = new Bridge(quad0, quad1); bridge = new Bridge(quad0, quad1); bridge = new Bridge(quad0, quad2); bridge = new Bridge(quad0, quad2); bridge = new Bridge(quad0, quad3); bridge = new Bridge(quad0, quad3); bridge = new Bridge(quad0, quad4); bridge = new Bridge(quad0, quad5); bridge = new Bridge(quad0, quad5); bridge = new Bridge(quad1, quad2); bridge = new Bridge(quad1, quad3); bridge = new Bridge(quad1, quad4); bridge = new Bridge(quad2, quad4); bridge = new Bridge(quad2, quad5); bridge = new Bridge(quad3, quad4); bridge = new Bridge(quad4, quad5); }//end LegalGraph }//end LegalGraph public class Bridge{ private Quadrant q0; private Quadrant q1; public Quadrant Q0{ [System.Diagnostics.DebuggerHidden()] get{ return this.q0; }//end get }//end Q0 public Quadrant Q1{ [System.Diagnostics.DebuggerHidden()] get{ return this.q1; }//end get }//end Q1 [System.Diagnostics.DebuggerHidden()] public override string ToString(){ return q0.Q.ToString() + "_" + q1.Q.ToString(); } public Bridge(Quadrant q0, Quadrant q1){ q0.Bridges.Add(this); q1.Bridges.Add(this); this.q0 = q0; this.q1 = q1; }//end Bridge }//end Bridge public class Quadrant{ private List bridges = new List(); private int quadrant; public List Bridges{ [System.Diagnostics.DebuggerHidden()] get { return this.bridges; }//end get }//end Bridges public int Q{ [System.Diagnostics.DebuggerHidden()] get{ return this.quadrant; }//end get }//end Quadrant public override string ToString() { return quadrant.ToString(); } public Quadrant(int quadrant) { this.quadrant = quadrant; } }//end class Quadrant private void HelpPlaySolutions(Bridge[] bridges, int index, Quadrant q){ if(index == 16) { //Win OnWin(bridges); } else{ /* * For each remaining bridge cross it, only if it hasn't been * crossed before. The magical nature of the graph ensures that all * moves are, in fact, legal if they have not been made before */ foreach(Bridge b in q.Bridges){ if(!Exists(bridges, index, b)) { bridges[index] = b; if(b.Q0 == q) HelpPlaySolutions(bridges, index + 1, b.Q1); else HelpPlaySolutions(bridges, index + 1, b.Q0); }//end if contains }//end foreach }//end if }//end HelpPlaySolutions private void PlaySolutions(){ foreach(Quadrant q in graph.quadrants){ ThreadPool.QueueUserWorkItem(new WaitCallback(ThreadGo), q); //ThreadGo(q); }//end foreach }//end PlaySolutions private void ThreadGo(object q){ DateTime now = DateTime.Now; if(q is Quadrant){ Bridge[] list = new Bridge[16]; HelpPlaySolutions(list, 0, (Quadrant)q); } OnThreadFinished((Quadrant)q, Guid.NewGuid().ToString(), DateTime.Now - now); }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.