N-Queens challenge

Question

I am doing an exhaustive search in N-queens code I wrote in C++. How can I optimize this code further?

It takes an input n (the number of queens) and returns a vector<vector<string>> having all possible arrangements. Looking at the code, I think the operations like pop_back() is slowing the entire runtime.

#include "stdafx.h"
#include "string"
#include "vector"
using namespace std;

   //Struct to store previously placed queens.
    struct rowCol {
       int row;
       int col;
       rowCol(int r, int c) {
        row = r;
        col = c;
       }
    };

class Solution {
public:
    bool check(int row, int col, vector<rowCol*>& history) {
        //check diagonals
        for (auto i : history) {
            if (abs(i->row - row) == abs(i->col - col))
                return 0;
        }
        //check columns
        for (auto i : history) {
            if (i->col == col)
                return 0;
        }
        return 1;
    }
    void recurse(vector<rowCol*>& history, int row, int n,vector<string>& res,vector<vector<string>>& result) {
        if (row < n) {
            for (int j = 0; j < n; j++) {
                if (check(row, j, history)) {
                    std::string x(n, '.'); 
                    history.push_back(new rowCol(row, j));
                    x[j] = 'Q';
                    res.push_back(x);
                    if (res.size() == n) {
                        result.push_back(res);
                    }
                    recurse(history, row+1, n, res,result);
                    res.pop_back();
                    history.pop_back();
                }
            }

        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<rowCol*> history;
        vector<string> res;
        recurse(history, 0, n,res,result);
        return result;
    }
};

int main()
{
    Solution s;
    s.solveNQueens(4);
    return 0;
}

Answer 1

Construct board string only when finished

Currently, you are constructing a bunch of strings to represent the rows of the board, but then you throw them away when the boards don't work out right. Instead of doing that, if you construct the full board only when you reach a solution, you can save time because you don't construct all the strings for the incorrect boards. Here is how I modified your program to do this, which made your program run 2x faster:

void recurse(vector<rowCol*>& history, int row, int n,vector<vector<string>>& result) {
    if (row < n) {
        for (int j = 0; j < n; j++) {
            if (check(row, j, history)) {
                history.push_back(new rowCol(row, j));
                if (row == n-1) {
                    // Got a solution.  Construct the whole board.
                    vector<string> res(n);
                    std::string x(n, '.');
                    for (int k = 0; k < n; k++) {
                        x[history[k]->col] = 'Q';
                        res[k] = x;
                        x[history[k]->col] = '.';
                    }
                    result.push_back(res);
                }
                recurse(history, row+1, n, result);
                history.pop_back();
            }
        }

    }
}
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<rowCol*> history;
    recurse(history, 0, n,result);
    return result;
}

Improving the rowCol history

Currently, you have a vector<rowCol *> history which holds all the previous queens you have placed. The first thing to notice is that history[i]->row is always equal to i, because you are placing queens one row at a time. So really you don't need a rowCol, only a col, which can just be a simple int.

The second thing to notice is that your code spends a lot of time pushing and popping to history. Instead of that, you could just make history be a vector of size n and just keep track of how many queens you have stored in it (which is just rows).

Here is how I have rewritten your program, which now runs 4x faster than the original:

class Solution {
public:
    bool check(int row, int col, vector<int>& history)
    {
        for (int i = 0; i < row; i++) {
            int col2 = history[i];
            if (col2 == col || row - i == abs(col2 - col))
                return 0;
        }
        return 1;
    }

    void recurse(vector<int>& history, int row, int n,
            vector<vector<string>>& result)
    {
        for (int col = 0; col < n; col++) {
            if (check(row, col, history)) {
                history[row] = col;
                if (row == n-1) {
                    // Solved it.  Create a board and store it.
                    vector<string> res(n);
                    std::string x(n, '.');
                    for (int i = 0; i < n; i++) {
                        x[history[i]] = 'Q';
                        res[i] = x;
                        x[history[i]] = '.';
                    }
                    result.push_back(res);
                } else {
                    // Go on to the next row.
                    recurse(history, row+1, n, result);
                }
            }
        }
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<string>> result;
        vector<int> history(n);
        recurse(history, 0, n, result);
        return result;
    }
};

Answer 2

I'd make history a vector<rowCol> instead of using pointers. You're allocating memory for a small struct (a slow operation), and not freeing it up, so it leaks.

I think the operations like pop_back() is slowing the entire runtime.

Don't think; measure it. pop_back is a fast operation, as no memory calls are made. push_back is also usually fast, but can take a bit longer when it needs to grow the storage. In your case, this will only happen once since the vectors are reused and the allocated space will never shrink.

Most of what you pass into recurse could be stored as members of the Solution class instead of passing them as parameters all the time.

Answer 3

Minor improvements over the answer by @jS1.

1. I would rename Solution to Solver.

2. I would use the following for Solution.

   using Solution = std::vector<std::string>;
   

3. I would use std::vector<Solution> for all the solutions.

4. I would simplify the lines that construct one solution.

Here's a program with those changes:

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>

using namespace std;

using Solution = std::vector<std::string>;

class Solver {
   public:
      bool check(int row, int col, vector<int>& history)
      {
         for (int i = 0; i < row; i++) {
            int col2 = history[i];
            if (col2 == col || row - i == abs(col2 - col))
               return 0;
         }
         return 1;
      }

      void recurse(vector<int>& history, int row, int n,
                   std::vector<Solution>& solutions)
      {
         for (int col = 0; col < n; col++) {
            if (check(row, col, history)) {
               history[row] = col;
               if (row == n-1) {
                  // Solved it.  Create the board.
                  Solution solution(n, std::string(n, '.'));
                  for (int i = 0; i < n; i++) {
                     solution[i][history[i]] = 'Q';
                  }
                  solutions.push_back(solution);
               } else {
                  // Go on to the next row.
                  recurse(history, row+1, n, solutions);
               }
            }
         }
      }

      vector<Solution> solveNQueens(int n)
      {
         vector<Solution> solutions;
         vector<int> history(n);
         recurse(history, 0, n, solutions);
         return solutions;
      }
};

int main(int argc, char** argv)
{
   Solver s;
   auto res = s.solveNQueens(std::atoi(argv[1]));
   for ( auto& solution : res )
   {
      std::cout << "-- Solution --" << std::endl;
      for ( auto& line : solution )
      {
         std::cout << line << std::endl;
      }
   }
   return 0;
}