title: What is the best way to route paths in a large grid?
body: <p>I'm working on an algorithm to find a set of non intersected paths in a grid for a 
  given pairs of points..
  Like this for these pairs:
  (9,4) and (12,13)
  <img src="https://i.stack.imgur.com/3ZW1M.png" alt="Sample Grid"></p>
  
  <p>The output should be something like this:</p>
  
  <pre><code>    9,10,11,7,3,4
  
      13,14,15,16,12
  </code></pre>
  
  <p>and print "Blocked" if it can't route all paths</p>
  
  <p>First I searched for an already made algorithm to find all simple paths between 2 
  points in a graph or a grid. and I found this one by @Casey Watson and @svick <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices">here</a>.. 
  It works really well but for small graphs only.</p>
  
  <p>I converted it to C#.NET and enhanced it a little bit to be able to find paths of 
  maximum length X. and build on it my total algorithm.</p>
  
  <p>The one I built works fine in small graphs..
  Here is routes 9 pairs in a 8x8 grid..
  <img src="https://i.stack.imgur.com/i3WJK.png" alt="enter image description here"></p>
  
  <p>but it takes a huge time in larger ones like the 16x16 or even the final one I intended to do which is a 3D model of 16x16x2
  Like this</p>
  
  <p><img src="https://i.stack.imgur.com/vR484.png" alt="8x8x2 grid"></p>
  
  <p>The algorithm was developed to be a depth first search <strong>RECURSIVE</strong> algorithm, but it 
  took a huge time to return value to the user. so I decided to convert it to loops instead of the recursive calls so that I can benefit from <strong>yield return</strong> feature in .NET
  but still it didn't help any better.</p>
  
  <p>The loops version of the algorithm find a route for a pair of points in less than a second but the recursive one took more than 90 seconds.</p>
  
  <p><img src="https://i.stack.imgur.com/lQT7O.png" alt="enter image description here"></p>
  
  <p>when I tried with 2 pairs, the loops version took around 342 seconds but the recursive one took around 200..</p>
  
  <p><img src="https://i.stack.imgur.com/OBM5M.png" alt="enter image description here"></p>
  
  <p>So I can't know which is faster..!? the recursive or the loops one..</p>
  
  <p>I really want to know the best way to do this..</p>
  
  <p>Note : the first digit in the number of the node determine the layer (Starts at 1)..</p>
  
  <p>Here is the code</p>
  
  <pre><code>    using System;
      using System.Collections;
      using System.Collections.Generic;
      using System.Diagnostics;
      using System.IO;
      using System.Linq;
  
      namespace AlgorithmTest
      {
       struct Connection
      {
      public int FirstNode;
      public int SecondNode;
  
      public Connection(int N1,int N2)
      {
          FirstNode = N1;
          SecondNode = N2;
      }
  }
  enum Algorithm
  { Recursion, Loops }
  
  public class Search
  {
  
      private const int MAX = 15;
  
      private const int Width = 16;
      private const int Length = 16;
      private const int Height = 2;
  
  
  
      private static void Main(string[] args)
      {
  
  
          var graph = new Graph();
  
  
          var str = new int[Height,Length, Width];
          var level = ((int)Math.Pow(10, (Length * Width).ToString().Length) &gt;= 100) ? (int)Math.Pow(10, (Length * Width).ToString().Length) : 100;              
          for (var i = 0; i &lt; Height; i++)
          {
              int num = 0;
              for (var j = 0; j &lt; Length; j++)
                  for (var k = 0; k &lt; Width; k++)
              {
                  str[i, j, k] = ++num + level;
  
              }
              level += level;
          }
  
  
          for (var i = 0; i &lt; Height; i++)
          {
              for (var j = 0; j &lt; Length; j++)
              {
                  for (var k = 0; k &lt; Width; k++)
                  {
  
                      if (i &lt; Height - 1) graph.addEdge(str[i, j, k], str[i + 1, j, k]);
                      if (i &gt; 0) graph.addEdge(str[i, j, k], str[i - 1, j, k]);
  
                      if (k &lt; Width - 1) graph.addEdge(str[i, j, k], str[i, j, k + 1]);
                      if (k &gt; 0) graph.addEdge(str[i, j, k], str[i, j, k - 1]);
  
                      if (j &lt; Length - 1) graph.addEdge(str[i, j, k], str[i, j + 1, k]);
                      if (j &gt; 0) graph.addEdge(str[i, j, k], str[i, j - 1, k]);
  
  
                  }
              }
          }
  
  
  
          var wt = new Stopwatch();
  
         wt.Start();
          var connectedNodes = new List&lt;Connection&gt;()
                                   {
  
  
  
                                       new Connection(1030, 1005),
         //                              new Connection(1002, 1044),
      //                                         new Connection(1015, 1064),
      //                                        new Connection(1041, 1038),
      //                                         new Connection(1009, 1027),
      //                                         new Connection(1025, 1018),
      //                                         new Connection(1037, 1054),
      //                                         new Connection(1049, 1060),
      //                                         new Connection(1008, 1031),
      //                                         new Connection(1001, 1035),
  
                                   };
          wt.Start();
          Console.WriteLine("Using Loops:");
          Console.WriteLine();
          var allPaths = new Search().FindAllPaths(connectedNodes, graph, MAX, Algorithm.Loops);
          wt.Stop();
          foreach (var path in allPaths)
          {
              PrintPath(path);
          }
          Console.WriteLine("Total Seconds: " + wt.Elapsed.TotalSeconds + ", Number of paths: " + allPaths.Count());
          Console.WriteLine("***************************************************************************************************");
          Console.WriteLine("Using Recursion:");
          Console.WriteLine();
          wt.Reset();
          wt.Start();
          allPaths = new Search().FindAllPaths(connectedNodes, graph, MAX, Algorithm.Recursion);
          wt.Stop();
          foreach (var path in allPaths)
          {
              PrintPath(path);
          }
          Console.WriteLine("Total Seconds: " + wt.Elapsed.TotalSeconds + ", Number of paths: " + allPaths.Count());
          Console.WriteLine();
  
      }
  
      private IEnumerable&lt;List&lt;int&gt;&gt; FindAllPaths(List&lt;Connection&gt; connectedNodes, Graph graph, int max, Algorithm algorithm)
      {
          var paths=new Stack&lt;List&lt;int&gt;&gt;();
          var blocked=new List&lt;int&gt;();
  
          for (var i = 0; i &lt; connectedNodes.Count; i++)
          {
              if (!blocked.Contains(connectedNodes[i].FirstNode)) blocked.Add(connectedNodes[i].FirstNode);
              if (!blocked.Contains(connectedNodes[i].SecondNode)) blocked.Add(connectedNodes[i].SecondNode);
          }
  
          if (algorithm == Algorithm.Recursion)
          {
              if (FindAllPaths(connectedNodes, 0, max, graph, paths, blocked))
              {
                  Console.WriteLine("BLOCKED");
                  return new List&lt;List&lt;int&gt;&gt;();
              }
          }
          else if(algorithm==Algorithm.Loops)
          {
              if (!FindAllPaths2(connectedNodes, 0, max, graph, paths, blocked))
              {
                  Console.WriteLine("BLOCKED");
                  return new List&lt;List&lt;int&gt;&gt;();
              }
          }
  
          return paths;
  
      }
      private static bool FindAllPaths(List&lt;Connection&gt; connectedNodes,int order,int max, Graph graph, Stack&lt;List&lt;int&gt;&gt; allPaths, List&lt;int&gt; blocked)
      {
  
          if (order &gt;= connectedNodes.Count) return false;
  
  
          var paths = SearchForPaths(graph, connectedNodes[order].FirstNode, connectedNodes[order].SecondNode, max, blocked);
          if (paths.Count == 0) return true;
          int i;
          for (i = 0; i &lt; paths.Count; i++)
          {
              var path = paths[i];
              allPaths.Push(path);
              blocked.AddRange(path);
  
  
              if (!FindAllPaths(connectedNodes, order + 1,max, graph, allPaths, blocked)) break;
  
              allPaths.Pop();
              foreach (var j in path)
              {
                  blocked.RemoveAll(num =&gt; num==j);
              }
  
              paths.RemoveAll(list =&gt; IsListsSimilar(list,path));
  
              i--;
  
          }
          if (i == paths.Count) return true;
  
  
          return false;
  
      }
  
      private static bool IsListsSimilar(List&lt;int&gt; L1,List&lt;int&gt; L2)
      {
          if (L2.Count &gt; L1.Count) return false;
  
          for (int i = 0; i &lt; L2.Count - 1; i++)
          {
              if (L1[i] != L2[i]) return false;
          }
          return true;
      }
  
      private static List&lt;List&lt;int&gt;&gt; SearchForPaths(Graph graph, int start, int end, int max, List&lt;int&gt; blocked)
      {
          blocked.Remove(start);
          blocked.Remove(end);
  
  
  
  
          var nodePaths = new List&lt;List&lt;int&gt;&gt;();
          var visited = new LinkedList&lt;int&gt;();
          visited.AddLast(start);
          DepthFirstSearch(graph, visited, end, max, blocked, nodePaths);
  
  
  
          nodePaths = nodePaths.OrderBy(list =&gt; list.Count).ToList();
  
          return nodePaths;
  
      }
      private static void DepthFirstSearch(Graph graph, LinkedList&lt;int&gt; visited, int end, int max, List&lt;int&gt; blocked, List&lt;List&lt;int&gt;&gt; paths)
      {
          var nodes = graph.adjacentNodes(visited.Last.Value);
          // examine adjacent nodes
          var nodeCount = blocked.Count;
          for (int i = 0; i &lt; nodeCount; i++)
          {
              if (visited.Contains(blocked[i])) return;
          }
  
          if (visited.Count &gt; max) return;
  
  
          nodeCount = nodes.Count;
          for (var i = 0; i &lt; nodeCount; i++)
          {
              if (visited.Contains(nodes[i]) || nodes[i] != end) continue;
  
              visited.AddLast(nodes[i]);
  
              {
                  paths.Add(new List&lt;int&gt;(visited));
  
              }
              visited.RemoveLast();
              break;
          }
  
  
  
          nodeCount = nodes.Count;
          for (var i = 0; i &lt; nodeCount; i++)
          {
              if (visited.Contains(nodes[i]) || nodes[i] == end) continue;
  
              visited.AddLast(nodes[i]);
              DepthFirstSearch(graph, visited, end, max, blocked, paths);
              visited.RemoveLast();
          }
  
      }
  
      private static bool FindAllPaths2(List&lt;Connection&gt; connectedNodes, int order, int max, Graph graph, Stack&lt;List&lt;int&gt;&gt; allPaths, List&lt;int&gt; blocked)
      {
  
          if (order &gt;= connectedNodes.Count) return false;
  
  
          foreach (var path in SearchForPaths2(graph, connectedNodes[order].FirstNode, connectedNodes[order].SecondNode, max, blocked))
          {
  
              allPaths.Push(path);
              blocked.AddRange(path);
  
  
              if (!FindAllPaths2(connectedNodes, order + 1, max, graph, allPaths, blocked)) break;
  
              allPaths.Pop();
              foreach (var j in path)
              {
                  blocked.RemoveAll(num =&gt; num == j);
              }
  
  
          }
  
  
  
  
          return true;
  
      }
      private static IEnumerable&lt;List&lt;int&gt;&gt; SearchForPaths2(Graph graph, int start, int end, int max, List&lt;int&gt; blocked)
      {
          blocked.Remove(start);
          blocked.Remove(end);
  
  
          var visited = new LinkedList&lt;int&gt;();
          visited.AddLast(start);
          foreach (var VARIABLE in DepthFirstSearch(graph, visited, end, max, blocked))
          {
              yield return VARIABLE;
          }
  
      }
      private static IEnumerable&lt;List&lt;int&gt;&gt; DepthFirstSearch(Graph graph, LinkedList&lt;int&gt; visited, int end, int max, List&lt;int&gt; blocked)
      {
  
  
  
  
  
          var nodes = graph.adjacentNodes(visited.Last.Value);
  
  
          var nodeCount = blocked.Count;
          for (int i = 0; i &lt; nodeCount; i++)
          {
              if (visited.Contains(blocked[i])) yield break;
          }
  
  
          if (visited.Count &gt; max) yield break;
  
          nodeCount = nodes.Count;
          for (var i = 0; i &lt; nodeCount; i++)
          {
              if (visited.Contains(nodes[i]) || nodes[i] != end) continue;
  
              visited.AddLast(nodes[i]);
  
              yield return (new List&lt;int&gt;(visited));
              visited.RemoveLast();
              break;
          }
  
  
  
  
          nodeCount = nodes.Count;
          for (var i = 0; i &lt; nodeCount; i++)
          {
              if (visited.Contains(nodes[i]) || nodes[i] == end) continue;
  
              visited.AddLast(nodes[i]);
              foreach (var P in DepthFirstSearch(graph, visited, end, max, blocked))
              {
  
                  yield return P;
  
              }
  
              visited.RemoveLast();
  
          }
  
  
  
  
  
  
      }
  
  
      private static void PrintPath(List&lt;int&gt; visited)
      {
  
          for (int i = 0; i &lt; visited.Count()-1; i++)
          {
              Console.Write(visited[i]);
              Console.Write(" --&gt; ");
          }
          Console.Write(visited[visited.Count() - 1]);
  
          Console.WriteLine();
          Console.WriteLine();
  
      }
  
  
  }
  public class Graph
  {
      private readonly Dictionary&lt;int, HashSet&lt;int&gt;&gt; map = new Dictionary&lt;int, HashSet&lt;int&gt;&gt;();
  
      public void addEdge(int node1, int node2)
      {
          HashSet&lt;int&gt; adjacent = null;
  
          map.TryGetValue(node1, out adjacent);
  
          if (adjacent == null)
          {
              adjacent = new HashSet&lt;int&gt;();
              map.Add(node1, adjacent);
          }
          adjacent.Add(node2);
      }
  
      public List&lt;int&gt; adjacentNodes(int last)
      {
          HashSet&lt;int&gt; adjacent = null;
  
          map.TryGetValue(last, out adjacent);
  
          if (adjacent == null)
          {
              return new List&lt;int&gt;();
          }
          return new List&lt;int&gt;(adjacent);
      }
  }
      }
  </code></pre>