N皇后问题与置换策略

Question

我想用置换方法为n皇后问题编写一个C++代码。这意味着我将皇后从1索引到n，棋盘的状态将由一个数组定义，其中第一项将皇后的行存储在第一列。显然，这样的数组将包含集合1，2，，n的排列。

我的第一次尝试是基于这样的想法:通过随机切换状态向量的两个条目来生成一个新的排列。这当然不是一种有效的方法，但我不知道如何修改Heap的算法，使它在每次调用它时返回一个新的排列。

我也在考虑使用boost的置换迭代器，但它看起来非常复杂。

这是代码：

// 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

这段代码似乎在某种意义上起作用，因为它返回了n皇后问题的解决方案。我想修改它(通过更改置换生成器)，以便它返回给定n的所有可能配置。

至于代码的效率，我想我可能只需要使用std::vector<unsigned>来存储每个皇后的行索引，但是代码的可读性可能会更低。

我还在想，也许我可以在编译时(而不是在构造函数中)通过使用constexpr实用函数来初始化queens变量？

这个问题主要是练习/学习我的C++技能的借口，所以我非常感兴趣的是关于代码质量的任何反馈，以及如何尽可能地改进这个简单的程序，遵循生产C++的良好实践。

Answer 1

避免声明

中的逗号运算符

在位置声明中使用逗号操作符。

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

最好分别声明每个变量，这样更容易找到变量声明，这样更容易添加和删除变量，并使代码更具可读性。

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

在许多情况下，最好使用size_t而不是unsigned int，特别是对于数组和向量索引。STL容器类的size()函数返回size_t。

factorial()函数

对factorial()函数使用迭代解决方案会更好，它的执行速度更快，内存也更少。虽然在这个程序中可能不会发生这种情况，但是对于大量的factorial()，当前的实现可能会由于堆栈上的factorial()副本的数量而导致堆栈溢出。使用迭代方法还可以测试要返回的值，以确保它不会超过所使用的变量的大小(算术溢出)。

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

一个很好的习惯是在if或else之后用括号({})包装操作。这提高了代码的可维护性。如果有人不得不在if语句之前添加另一条语句来修改return语句，那么如果没有添加方括号，他们就会引入一个bug。

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

算法

如果类Queens有一种方法打印queens向量的内容，这样main()函数会更简单一些，因为solve()函数可以返回true或false，并且代码不会使用try{}和catch{}。通常，try{}和catch{}用于错误处理，引发的是异常。找不到N皇后问题的解决方案不应被视为错误，也不应使用“尝试和捕捉”。这也将消除main()对私有向量queens或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";
    }
}