Program to find number of hamiltonian paths in a graph given start and end points

Question

Given a graph with n² pathing nodes, and given that the starting node is always in the top right corner (point A) and the ending node is always in the bottom right corner (point B), I need to write a C# program that will determine the number of hamiltonian paths from A to B given n (assuming n <=10). In other words, I need to find every path starting at A and ending at B, where each node is visited once and only once, and movement among the nodes is restricted to left, right, up, down (no diagonals).

For example, if n = 5, then one possible path would be the one shown in this image:

Ideally, I would like to develop an intelligent algorithm that utilizes some heuristics, but for now I just need to develop a brute force method to start with. I am assuming that I use a breadth first search, but I really don't know where to begin in implementing that using C#.

Answer 1

Some bruteforce thing

Build the Graph. Build a Graph runner. Cache all Runinformation. Make the runner rerun the graph and exclude all decisions from the Runinformation. When the runner cant run anymore filter the cached data and count the result.

Implementing in C#

Install a testframework like nunit. write a list of features you need.

repeat until featurelist is empty:

• select the smallest feature
• write a failing test
• write code to pass the test
• ensure all tests pass
• refactor to make pritty
• clear item from featurelist

done

---

Edited to answer some of the questions in the comments

• You can download nunit from the internet. Unpack it to a folder of your choice.
• Create an empty console application.
• Explore the NUnit directory to find the framework, add that framework to your project.
• Explore the NUnit directory to find the gui runner, add it to your project.
• We actually dont want to run the project with a console, we just dont want a form to be autocreated, open the properties and redeclare your project to be a windows application.
• replace your program.cs with the code below.
• compile and run. click run in the gui and press F5 if exceptions come up
• congratulations - you just used nunit

Here is the program:

using System;
using NUnit.Framework;
namespace EC_Connect_Test
{
    class Program
    {
        [STAThread]
        static void Main(string[] args)
        {
            string fullPath = System.Reflection.Assembly.GetAssembly(typeof(Program)).Location;
            NUnit.Gui.AppEntry.Main(new string[] { fullPath });
        }
    }
        public class MathClass
        {
            internal static double Divide(int A, int B)
            {
                if (B == 0) throw new DivideByZeroException();
                return (Double)A / (Double)B;
            }
        }

        [TestFixture]
        class MyFirstTestClass
        {
            [Test]
            public void DividingTwoIntegersResultIsDouble()
            {
                Double expected = 3.3;
                Double actual = MathClass.Divide(33, 10);
                Assert.AreEqual(expected, actual);
            }

            [Test]
            public void DividingByZeroShouldThrow()
            {
                Assert.Throws<DivideByZeroException>(
                    () => { MathClass.Divide(33, 0); }
                );
            }
        }

    }

You can also start Nunit externally and give it your debugproject as a directory. That way exceptions dont come up and testing gets easier.

A featurelist is simply the things you want your software to do. In your case you are supplied with a given graph in some form. That could be a file or a piece of paper. So one feature is to loading that information and making a graph from it. The next feature you mentioned is that your program should check n<=10 and refuse to work if it isnt so, thats a feature too. Another one is to return the results through a given interface. And last not least is the ability to actually find all connections. If you list those for yourself you can select the one you think is easiest and start with that one.

When testing dont forget to create end to end tests for known cases. so fixed graph in, known number out.

Using the wild assumption your graph is in a textfile where each line lists ist connections to other lines you could write tests like this:

    [TestFixture]
    class graphloadingSpex
    {
        String[] lines = new String[] {
        "2,3,4",
        "1",
        "1,4",
        "1,3"
        };

        [Test]
        public void ShouldShowConnectionsAfterLoading()
        {
            Graph tested = new Graph(lines);
            Assert.AreEqual(new String[] { "2", "3", "4" }, tested["1"].GetConnextions());
            Assert.AreEqual(new String[] { "1"}, tested["2"].GetConnextions());
            Assert.AreEqual(new String[] { "1", "4" }, tested["3"].GetConnextions());
            Assert.AreEqual(new String[] { "1", "3" }, tested["4"].GetConnextions());
        }
    }

This will not compile since Graph does not exist yet. But getting it to compile and making the test pass would satisfy your first feature and you could go on implementing the next one by writing the test first.