C++ Backtracking in a 2D vector
<p>I am currently trying to use backtracking in order to generate all the different positions a word could have in a 2D vector.</p>
<p>Let's say that I have a vector (which I prefer to use for memory reasons as I will be treating a lot of words) containing the word 'Hello'.</p>
<p>I generate a 2D vector of '.' characters 5x5 wide (so it can fit the word).</p>
<p>And then using a backtracking algorithm, I would like to generate all the positions this word could take with the letters <strong>still linked to each other</strong>.</p>
<p>For example :</p>
<pre><code> . . . . .        . . . . .              . . . . .
 H e . . .   or   . . . H .    or even   . . . . .
 . l . . .        . . o e .              . . . . .
 . l o . .        . . l l .              . . . . .
 . . . . .        . . . . .              o l l e H
</code></pre>
<p>The algorithm I am interested in for 1D is (pseudo code):</p>
<hr />
<pre><code>function solve(word vector, size of vector) 

  if end of word vector
     Print vector obtained

   else for choice possible do
         if Choice is admissible then 
             Build partial Candidate according to Choice 
             Test(i + 1) 
             Undo Choice
</code></pre>
<hr />
<p>This pseudo code could give the different combinations of letters in a word. I'm trying to adapt it to make it do what explained before.</p>
<p>Sadly I'm implementing it wrong because I don't obtain the results expected at all : Nothing prints. I would be pleased to read your remarks and opinions on this.</p>
<p>Here is what I did so far :</p>
<h3>Backtracking function :</h3>
<pre><code>// All the arguments of the function are correctly defined in the main, with i, j, k set to zero.

bool backtracking(vector&lt;vector&lt;char&gt; &gt; vect , vector &lt;char&gt; word,int n, int i, int j, int k) {

    if(k==n)    // If the end of the word is reached
    {
        print_grid(vect);  //Prints the 2D vector with the word included
        return true;
    }
    
    else    
    {
        
        if(admissible_choice(vect, n, i, j) == true) // If choice is admissible
        {
            
            vect[i][j] = word[k];                   // Builds partial candidate
            
            if (backtracking(vect,word,n,i+1,j,k)==true) // Moves in the i-direction
            {   k++;                    // If true, goes to the next element of the chain
                return true;        }
            
            if (backtracking(vect,word,n,i,j+1,k)==true) // Moves in the j direction
            {   k++;
                return true;        }
                    
            else
            {   vect[i][j] = '.';           // Backtrack, if no condition verified then fills the 2D vector with points
                
                return false;       }
        }
 
    return false;
    }
        
}   
</code></pre>
<h3>Printing function</h3>
<pre><code>void print_grid(vector&lt;vector&lt;char&gt; &gt; vect) {
    for (int i = 0; i &lt; vect.size(); i++)  {
        for (int j = 0; j &lt; vect[i].size(); j++) {
            cout &lt;&lt; vect[i][j]; 
        }
        cout&lt;&lt;&quot;&quot;&lt;&lt;endl;
    }
    cout&lt;&lt;&quot;\n&quot;&lt;&lt;endl;   
}
</code></pre>
<h3>Function to determine admissible choices</h3>
<pre><code>bool admissible_choice(vector&lt;vector&lt;char&gt; &gt; vect, int n, int i, int j)
{
    if(i &gt;= 0 &amp;&amp; i &lt; n &amp;&amp; j &gt;= 0 &amp;&amp; j &lt; n &amp;&amp; vect[i][j] == '.')
    {   return true;}

    else
    {   return false;}
}
    
</code></pre>
<p>Thanks in advance for all the help you could provide !</p>