title: M-Color graph using iterative BFS - how to backtrack
body: <p>I am attempting to do backtracking while trying to solve the m-coloring problem. I know there are recursive solutions out there but I wanted to take a stab at an iterative solution. My attempt to backtrack is shown in the code. The program gives me a correct answer for the test cases I have run. I would like to know if my method of backtracking is correct.</p>
  
  <p>When I have to backtrack I pop all elements of the current queue before putting the current vertex onto the queue. </p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;queue&gt;
  #include &lt;iostream&gt; 
  // Number of vertices in the graph
  #define V 4
  int colorArr[V];
  bool graphColoring(bool graph[][V], int m)
  {
      // Create a color array to store colors assigned to all veritces. Vertex 
      // number is used as index in this array. The value '-1' of  colorArr[i] 
      // is used to indicate that no color is assigned to vertex 'i'. 
  
      for (int i = 0; i &lt; V; ++i)
          colorArr[i] = -1;
  
      int colors[V][3] = {{1,2,3},{1,2,3},{1,2,3},{1,2,3}}; //all possible colors for each vertex...if -1 means that color is impermissible
      // Assign first color to source
      colorArr[0] = colors[0][0];
  
      // Create a queue (FIFO) of vertex numbers and enqueue source vertex
      // for BFS traversal
      std::queue &lt;int&gt; q;
      q.push(0);
  
      // Run while there are vertices in queue (Similar to BFS)
      while (!q.empty())
      {
          // Dequeue a vertex from queue ( Refer http://goo.gl/35oz8 )
          int u = q.front();
          q.pop();
           // Find all non-colored adjacent vertices
          for (int v = 0; v &lt; V; ++v)
          {
              // An edge from u to v exists and destination v is not colored
              if (graph[u][v] &amp;&amp; colorArr[v] == -1)
              {
                  // Assign alternate color to this adjacent v of u
                  for (int c = 0; c &lt; m; c++)
                  {
                      if (((c+1) != colorArr[u]) &amp;&amp; (colors[v][c] != -1)) {
                          colorArr[v] = colors[v][c];
                          break;
                      }
                      else if (c== (m-1)) // all colors are impermissible for vertex v therefore return false
                          return false;
                  }    
                  q.push(v);
              }
  
              //  An edge from u to v exists and destination v is colored with
              // same color as u
              else if (graph[u][v] &amp;&amp; (colorArr[v] == colorArr[u])) 
              {
                  colors[v][colorArr[u]-1] = -1; // mark this is impermissible
                  colorArr[v] = -1; // recompute color again
                  int count = 0;
                  for (int c = 0; c &lt; m; c++)
                  {
                      if (colors[v][c] == -1)
                      {
                          count++;
                          if (count == m) // if all are impermissible, then return false  
                              return false;
                      }
                  }
                  // Pop all elements in preparation for backtracking
                  while (!q.empty())
                      q.pop();
                  q.push(u); //MY ATTEMPT TO BACKTRACK??? 
              }
          }
      }
  
      // If we reach here, then all adjacent vertices can be colored with 
      // alternate color
      return true;
  }
  /* A utility function to print solution */
  void printSolution(int color[])
  {
      printf("Solution Exists:"
              " Following are the assigned colors \n");
      for (int i = 0; i &lt; V; i++)
        printf(" %d ", color[i]);
      printf("\n");
  }
  
  // driver program to test above function
  int main()
  {
      /* Create following graph and test whether it is 3 colorable
        (3)---(2)
         |   / |
         |  /  |
         | /   |
        (0)---(1)
      */
      bool graph[V][V] = {{0, 1, 1, 1},
          {1, 0, 1, 0},
          {1, 1, 0, 1},
          {1, 0, 1, 0},
      };
      int m = 3; // Number of colors
      bool solution = graphColoring (graph, m);
      if (solution)
          printSolution(colorArr);
     return 0;
  }
  </code></pre>