皇后问题 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki

感觉皇后问题好高大上，用 C++ 十行代码实现，就可以有 15k 待遇！

我想了一个小时，甚至边吃饭边想，发现这个可以用递归算法解决。简而言之，在当前 chessboard 对象里按一定的索引规律，找出依次相邻的两个空 board, 分别叫 first_empty_board, second_empty_board 吧。各自填充进一个皇后并更新整个 chessboard, 如此反复双弹递归，直到再也填充不下。如果填充的皇后数等于棋盘长度，那么这就是一个有效的解 solution，push 进全局变量 g_solutions 即可。

但时间复杂度高达指数阶！不过据说现在没有多项式时间复杂度算法，这么一来我在递归思想上应该合格了吧？（窃笑

刚开始动写代码，纠结用什么数据结构了半天。用二维数组？但传函数形参好麻烦；用 std::vector? 但代码肯定又冗长无比。后来我决定还是用后者好了，毕竟一样可以用索引操作符。不过 @innocentim 启发了我，可以把算法与数据结构分开做，优先解决好算法问题，即用最简单的固定长度一维全局数组，搞定算法后再优化数据结构也不迟。

不过我硬是用上了一个 std::vector<std::vector<bool>>. 具体代码如下。

#include <algorithm>
#include <cassert>
#include <set>
#include <utility>
#include <vector>

using BoardIndex = std::pair<int, int>;
std::pair<int, int> g_invalid_board(0, 0);
std::set<std::set<BoardIndex>> g_solutions;

std::pair<BoardIndex, BoardIndex> TwoEmptyBoard(
    std::vector<std::vector<bool>> cheesboard) {
  bool is_first_found = false;
  BoardIndex first_empty_board = g_invalid_board;
  BoardIndex second_empty_board = g_invalid_board;
  int row = 1;
  for (auto longboard : cheesboard) {
    int column = 1;
    for (auto board : longboard) {
      if (board == false && !is_first_found) {
        first_empty_board = std::pair<int, int>(row, column);
        is_first_found = true;
      } else {
        second_empty_board = std::pair<int, int>(row, column);
      }
      ++column;
    }
    ++row;
  }
  return std::pair<BoardIndex, BoardIndex>(
      first_empty_board,
      second_empty_board);
}

void FillBoard(
    BoardIndex queen_board,
    std::vector<std::vector<bool>> cheesboard) {
  int row = queen_board.first;
  int column = queen_board.second;
  for (auto iterator = cheesboard[row].begin();
      iterator != cheesboard[row].end();
      ++iterator) {
    *iterator = true;
  }
  for (auto iterator = cheesboard.begin();
      iterator != cheesboard.end();
      ++iterator) {
    (*iterator)[column] = true;
  }
}

void Solute(
    std::vector<std::vector<bool>> cheesboard,
    std::set<BoardIndex> solution) {
  assert(number >= 0);
  if (solution.size() == cheesboard.size()) {
    g_solutions.insert(solution);
    return;
  }
    
  auto two_empty_cheesboard = TwoEmptyBoard(cheesboard);
  auto temporary_cheesboard = cheesboard;  // use for second_empty_board
  auto first_empty_board = two_empty_cheesboard.first;
  if (first_empty_board != g_invalid_board) {
    FillBoard(first_empty_board, cheesboard);
    solution.insert(first_empty_board);
    Solute(cheesboard, solution);
  }
  auto second_empty_board = two_empty_cheesboard.second;
  if (second_empty_board != g_invalid_board) {
    FillBoard(second_empty_board, temporary_cheesboard);
    solution.insert(second_empty_board);
    Solute(temporary_cheesboard, solution);
  } 
}

// int main(int argc, char *argv[]) {
  // return 0;
// }

一共 79 行，事实上我在写 FillBoard 时就放弃继续实现了，横竖填充还好，但写填充斜行的代码就痛不欲生！于是连同 main 里的测试也不写了，如今我很惊叹究竟要用怎样巧夺天工的数据结构，才能代码仅十行就大破八皇后之问。此外此代码实现也有很多地方让我不安，比如用到了不少全局变量，那当分离式编译此代码时，其定义顺序行为未定义；Solute 找出两个空 board 的代码略冗余，有太多的复制构造销毁开销了；此外索引也很令人头痛，代码中有些索引值是错的。

GAME OVER. (:з」∠)

皇后问题 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️