2
\$\begingroup\$

I would like to write a C++ code for the n-queens problem using the permutation approach. This means I index the queens from 1 to n, and the state of the checkerboard will be defined by an array where the i-th entry stores the row of the queen at the i-th column. Clearly, such array will contain a permutation of the set [1, 2, ..., n].

My first attempt is based on the idea to generate a new permutation by switching two entries of the state vector at random. This certainly is not an efficient way of doing this, but I do not know how to modify Heap's algorithm so that it returns a new permutation every time I call it.

I was also thinking about using boost's permutation iterator but it seems very complicated.

This is the code:

// queens.cc
#include <iostream>
#include "queens.h"


int main() {
    Queens<8> a;
    try {
        auto q = a.solve();
        std::cout << a.length() << "\n";
        std::cout << "found configuration:\n";
        for (auto it : q) {
            std::cout << it.col << " " << it.row << "\n";
        }
        std::cout << std::flush;
    } catch (const char* msg) {
        std::cerr << msg << std::endl;
    }
}
// queens.h
#ifndef QUEENS_H
#define QUEENS_H
#include <random>
#include <vector>


typedef struct {
  unsigned int row, col;
} Position;


constexpr unsigned int factorial(const unsigned int n) {
    if (n == 1)
        return 1;
    else
        return n*factorial(n - 1);
}


template <unsigned int N>
class Queens {
public:
  Queens();
  std::vector<Position>::size_type length() const { return queens.size(); };
  std::vector<Position>& solve();
private:
  // Used for generating the permutations.
  std::default_random_engine generator;
  std::uniform_int_distribution<unsigned int> distribution{1, N};
  // The coordinates of the queens.
  std::vector<Position> queens{N};

  void generate_permutation();
  bool configuration_acceptable(const std::vector<Position>&) const;
};



template<unsigned int N>
Queens<N>::Queens() {
    for (unsigned int i = 1; i <= N; ++i) {
        queens[i - 1].col = i;
        queens[i - 1].row = i;
    }
}


// Keeps generating new permutations by random swap.
template<unsigned int N>
void Queens<N>::generate_permutation() {
    auto i = distribution(generator);
    auto j = distribution(generator);
    auto ri = queens[i - 1].row;
    queens[i - 1].row = queens[j - 1].row;
    queens[j - 1].row = ri;
}


// Given the queens's position c, returns true if the queens are not attacking
// each other, otherwise false.
template<unsigned int N>
bool Queens<N>::configuration_acceptable(const std::vector<Position>& c) const {
    for (auto i = 0; i < c.size() - 1; ++i) {
        auto qi = c[i];
        for (auto j = i + 1; j < c.size(); ++j) {
            auto qj = c[j];
            auto delta = qj.col - qi.col;
        if (qj.row == qi.row + delta || qj.row == qi.row - delta)
            return false;
        }
    }
    return true;
}


// Sweeps through all permutations of (1..N) and returns the first one that
// fulfills the constraints.
template<unsigned int N>
std::vector<Position>& Queens<N>::solve() {
    for (unsigned int i = 0; i < factorial(N); ++i) {
        generate_permutation();
        if (configuration_acceptable(queens))
            return queens;
    }
    throw "Solution not found";
}

#endif

The code seems to be working in the sense that it returns a solution to the n-queen's problem. I would like to modify it (by changing the permutation generator) so that it returns all the possible configurations for a given n.

As for the efficiency of the code, I guess I could probably just use an std::vector<unsigned> for storing the row index of every queen, but the code would probably be less readable.

I was also thinking that maybe I could initialise the queens variable at compile time rather than in the constructor, by using a constexpr utility function?

This problem is mostly an excuse to practice/learn my C++ skills, so I am very interested on any feedback on the code quality and on how to improve this simple program as much as possible, following good practices for production C++.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I believe you can use backtracking to generate all possible solutions. \$\endgroup\$
    – Sriv
    Nov 23, 2019 at 14:45
  • \$\begingroup\$ Welcome to code review, where we review working code and provide suggestions on how that code can be improved. Unfortunately we can't really provide you with an alternate method for solving the problem. \$\endgroup\$
    – pacmaninbw
    Nov 23, 2019 at 15:02
  • \$\begingroup\$ @pacmaninbw thanks, I would be happy just to have a review on the code I posted, without any comment on how to improve the algorithm. \$\endgroup\$
    – J. D.
    Nov 23, 2019 at 21:40

1 Answer 1

2
\$\begingroup\$

Avoid the Comma Operator in Declarations

In the declaration of Position the comma operator is being used.

typedef struct {
    unsigned int row, col;
} Position;

It is preferable to declare each variable separately, it is easier to find variable declarations this way, it is easier to add and remove variables this way and it makes the code more readable.

typedef struct {
    size_t row;
    size_t col;
} Position;

In many cases it is preferable to use size_t instead of unsigned int, especially for array and vector indexes. The size() function of STL container classes returns size_t.

The factorial() Function

It would be better to use an iterative solution for the factorial() function, it would perform faster and use less memory. While this probably won't happen in this program, for large numbers the current implementation of factorial() may cause a stack overflow due to the number of copies of factorial() on the stack. Using an iterative approach would also allow for testing the value to be returned to make sure it never exceeds the size of the variable being used (Arithmetic Overflow).

constexpr unsigned int factorial(const unsigned int n) {
    if (n == 1)
        return 1;
    else
        return n*factorial(n - 1);
}

A good habit to get into is to wrap actions after if or else in brackets ({}). This improves the maintainability of the code. If someone had to modify the if statement by adding another statement before the return statement they could introduce a bug if the didn't add the brackets.

constexpr unsigned int factorial(const unsigned int n) {
    if (n == 1) {
        return 1;
    }
    else {
        return n*factorial(n - 1);
    }
}

Algorithm

It might be better if the class Queens had a way to print the contents of the queens vector, that way the main() function would be simpler, because the solve() function could return true or false and the code would not be using try{} and catch{}. Generally try{} and catch{} are used for error processing, and what is thrown is an exception. Not finding a solution to the N Queens problem should not be considered an error and shouldn't use try and catch. This would also remove any necessity for main() to have any knowledge of the private vector queens or the struct Position

template<unsigned int N>
bool Queens<N>::solve() {
    for (unsigned int i = 0; i < factorial(N); ++i) {
        generate_permutation();
        if (configuration_acceptable(queens))
        {
            return true;
        }
    }
    return false;
}

template<unsigned int N>
void Queens<N>::printQueens()
{
    for (auto it : queens) {
        std::cout << it.col << " " << it.row << "\n";
    }
    std::cout << std::flush;
}

int main() {
    Queens<8> a;
    bool solved = a.solve();
    std::cout << a.length() << "\n";
    if (solved)
    {
        std::cout << "found configuration:\n";
        a.printQueens();
    } else {
        std::cout << "No Solution Found\n";
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Thanks. I guess it is a good practice to use brackets every time we write a for loop, even if it is a one-line action. As for the printQueens member function, would you recommend doing this instead: ` template<size_t N2> friend std::ostream& operator<<(std::ostream& s, const Queens<N2>& q) { for (auto it : q.queens) { s << it.col << " " << it.row << "\n"; } s << std::flush; return s; } ` And then calling: ` if (solved) { std::cout << a; } else { std::cerr << "Solution not found." << std::endl; } ` \$\endgroup\$
    – J. D.
    Nov 25, 2019 at 13:39
  • \$\begingroup\$ That's a good alternative. \$\endgroup\$
    – pacmaninbw
    Nov 25, 2019 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.