title: Backtrack algorithm, Stack overflow error, despite heap allocation
body: <p>I'm currently working on a program that has to solve a 10x10 char maze, for example this one: </p>
  
  <pre><code>      1   2   3   4   5   6   7   8   9  10
  ___________________________________________
   1|   +  []   +  []   +  []   +   +   +  []
   2|   +  []   +   +  []   +   +  []  []  []
   3|   +   +  []  []  []   +  []  []   +   +
   4|  []  []  []  []   +   +   +  []  []   +
   5|   +  []   +  []   +  []   +   +   +  []
   6|   +   +   +   +   +   +  []  []   +  []
   7|  []   +   +   +  []  []   +   +   +  []
   8|   +   +   +  []   +   +   +  []  []   +
   9|   +   +   +  []  []   +   +  []  []   +
  10|   +  []   +  []   +   +  []   +   +   +
  </code></pre>
  
  <p>Ignore the numbers, they are just coordinates. As for <code>[]</code> it's just the way the maze is printed. In actuality wherever there's a <code>+</code> then that means path, wherever there's <code>[]</code> that means there's an obstacle.</p>
  
  <p>I'm using the backtrack algorithm: </p>
  
  <pre><code>void backtrack(int curX, int curY, char(*char_maze)[10], int position)
  {
      if (curX &lt; 0 || curY &lt; 0 ||
          curX &gt; 9 || curY &gt; 9) {
          //out of bounds
          return;
      }
      Node tmp;
      tmp.x = curX, tmp.y = curY;
      queue(&amp;head, &amp;tmp);
      position++;
      if (char_maze[curX][curY] == finish) {
          //destination found TODO print path
          printf("route found");
      }
      if (char_maze[curX][curY] == path) {
          char_maze[curX][curY] = visited;
      }
      backtrack(curX, curY - 1, char_maze, position);
      backtrack(curX - 1, curY, char_maze, position);
      backtrack(curX, curY + 1, char_maze, position);
      backtrack(curX + 1, curY, char_maze, position);
  
      char_maze[curX][curY] = path;
      if (position) {
          del_nth(head, position);
      }
      if (!position) {
          del_first(&amp;head);
      }
      position--;
  }
  </code></pre>
  
  <p>The correct route will consist of a linked list, here's a node of that list: </p>
  
  <pre><code>typedef struct coords {
      int     x;
      int     y;
      struct coords * next;
  }Node;
  </code></pre>
  
  <p>whenever  <code>backtrack(...)</code> stumbles over a passable cell, it's supposed to mark it as visited and add it to the list. Adding to the list is done by these 2 functions:</p>
  
  <pre><code>void queue(Node ** head, Node * object)
  {
      Node * tmp = (Node *)malloc(sizeof(Node)); //this is the problematic line
      *tmp = *object;
      Node * last = get_last(*(head));
      if (!last) {
          (*head) = tmp;
          tmp-&gt;next = NULL;
      }
      else {
          last-&gt;next = tmp;
          tmp-&gt;next = NULL;
      }
  }
  </code></pre>
  
  <p>and </p>
  
  <pre><code>Node * get_last(Node * head)
  {
      while (1) {
          if (head) {
              head = head-&gt;next;
          }
          else {
              return NULL;
          }
      }
  return head;
  }
  </code></pre>
  
  <p>and also under the appropriate conditions <code>backtrack(...)</code> should unmark a cell and delete it from the list. Deletion is done using these 2 functions: </p>
  
  <pre><code>void del_nth(Node * head, int index)
  {
      Node * previous;
      for (int i = 0; i &lt; index - 1; i++) {
          head = head-&gt;next;
      }
      previous = head;
      head = head-&gt;next;
      previous-&gt;next = head-&gt;next;
      free(head);
  }
  </code></pre>
  
  <p>and </p>
  
  <pre><code>void del_first(Node ** head)
  {
      Node * del = (*head);
      (*head) = (*head)-&gt;next;
      free(del);
  }
  </code></pre>
  
  <p><code>path, visited, finish</code> and so on are <code>const char</code>-s, which represent the cells of the maze.</p>
  
  <pre><code>backtrack(...)
  </code></pre>
  
  <p>is called with 2 coordinates set by the user, the maze itself and <code>position</code> which is set to <code>0</code>.</p>
  
  <p>Now that I explained how the code works, the problem. I've ran this code through the Visual Studio Debugger and I got a <code>Stack overflow (parameters: 0x00000001, 0x00492FFC).</code> exception on this line </p>
  
  <pre><code>Node * tmp = (Node *) malloc(sizeof(Node)); 
  </code></pre>
  
  <p>which is a part of the <code>queue(...)</code> function. This doesn't make any sense to me, since <code>malloc()</code> allocates on the heap. I'm stumped, I'm out of explanations, I have no idea why this happens. I included all of the code used in the <code>backtrack(...)</code> function because the problem may actually be there. It wouldn't be the first time a debugger pointed out a wrong line.
  Anyway, many thanks for your help in advance. </p>