C++ Backtracking in a 2D vector

Question

I am currently trying to use backtracking in order to generate all the different positions a word could have in a 2D vector.

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'.

I generate a 2D vector of '.' characters 5x5 wide (so it can fit the word).

And then using a backtracking algorithm, I would like to generate all the positions this word could take with the letters still linked to each other.

For example :

 . . . . .        . . . . .              . . . . .
 H e . . .   or   . . . H .    or even   . . . . .
 . l . . .        . . o e .              . . . . .
 . l o . .        . . l l .              . . . . .
 . . . . .        . . . . .              o l l e H

The algorithm I am interested in for 1D is (pseudo 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

---

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.

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.

Here is what I did so far :

Backtracking function :

// All the arguments of the function are correctly defined in the main, with i, j, k set to zero.

bool backtracking(vector<vector<char> > vect , vector <char> 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;
    }
        
}   

Printing function

void print_grid(vector<vector<char> > vect) {
    for (int i = 0; i < vect.size(); i++)  {
        for (int j = 0; j < vect[i].size(); j++) {
            cout << vect[i][j]; 
        }
        cout<<""<<endl;
    }
    cout<<"\n"<<endl;   
}

Function to determine admissible choices

bool admissible_choice(vector<vector<char> > vect, int n, int i, int j)
{
    if(i >= 0 && i < n && j >= 0 && j < n && vect[i][j] == '.')
    {   return true;}

    else
    {   return false;}
}
    

Thanks in advance for all the help you could provide !

Answer 1

Here you go. There is a fundamental difference between kicking off the search at some point, and proceeding from one valid point to the next point. So in this code, place_word iterates through all possible grid positions, calling the recursive backtracking for each point.

backtracking needs to search, not just the incremented coordinates, but also the decremented coordinates. Where place_word only increments its coordinates -- I think your original attempt was trying to combine these concepts into one unit of code.

I also chose to pass the 2D grid vector by reference and undo any changes made by the recursive function before it returns. This way, only one grid object is used by the search, while passing by value incurs a lot of overhead by making a new copy of the grid each time backtracking is called.

I needed to rename some of the variables to help me understand what was going on. I also removed dimension variables which were redundant because they were already available as vector sizes.

#include <iostream>
#include <vector>
#include <algorithm>

// admissible_choice returns true when the point at (x,y) is inside the grid,
// and is also unpopulated.
bool admissible_choice(std::vector<std::vector<char> > grid, int x, int y) {
    return x >= 0
        && x < static_cast<int>(grid.front().size())
        && y >= 0
        && y < static_cast<int>(grid.size())
        && grid[y][x] == '.';
}

void print_grid(std::vector<std::vector<char> > const& grid) {
    for(const auto& line : grid) {
        for(auto ch : line) {
            std::cout << ch;
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

// backtracking performs a depth-first recursive search for valid word positions
void backtracking(std::vector<std::vector<char> > &grid, std::vector<char> const& word, int x, int y, int wi=0) {
    if(!admissible_choice(grid, x, y)) {
        return;
    }

    grid[y][x] = word[wi];

    if(++wi == word.size()) {
        print_grid(grid);
    } else {
        backtracking(grid, word, x+1, y, wi);
        backtracking(grid, word, x-1, y, wi);
        backtracking(grid, word, x, y+1, wi);
        backtracking(grid, word, x, y-1, wi);
    }
    grid[y][x] = '.';
}

// place_word initializes backtracking recursion, for every
// possible starting point for a word placed in a grid
void place_word(std::vector<std::vector<char> > &grid, std::vector<char> const& word) {
    const int width = static_cast<int>(grid.front().size());
    const int height = static_cast<int>(grid.size());
    for(int y=0; y<height; ++y) {
        for(int x=0; x<width; ++x) {
            backtracking(grid, word, x, y);
        }
    }
}

// ToVector converts a char string literal to a vector
template <std::size_t N>
std::vector<char> ToVector(const char (&str)[N]) {
    return std::vector<char>(&str[0], &str[N-1]);
}

// InitGrid returns a grid with the given dimensions in its unpopulated state
std::vector<std::vector<char> > InitGrid(std::size_t width, std::size_t height) {
    std::vector<std::vector<char> > grid(height);
    for(auto& line : grid) {
        line.assign(width, '.');
    }
    return grid;
}

int main() {
    auto word = ToVector("Hello");
    auto grid = InitGrid(word.size(), word.size());

    place_word(grid, word);
}