N皇后两种解法（C++实现）

/*
 * NQueens.h
 *
 *  Created on: 2020年3月2日
 *      Author: LuYonglei
 */

#ifndef SRC_NQUEENS_H_
#define SRC_NQUEENS_H_
#include <iostream>
using namespace std;

class Queen {
public:
    Queen(int size_) :
            size(size_ <= 0 ? 8 : size_), columns(new int[size]), way(0) {
    }
    ~Queen() {
        delete[] columns;
    }
    void placeQueens() {
        //摆放皇后
        place(0);
        cout << "共有 " << way << " 组解法。" << endl;
    }
private:
    //place进行回溯操作
    void place(int row) {
        //在第row行放置棋子
        if (row == size) {
            //如果全部摆放完成就返回
            show();
            way++;          //摆放+1
            return;
        }
        for (int col = 0; col < size; col++) {
            //第row行，第col列可以摆放
            if (isValid(row, col)) {
                columns[row] = col;
                place(row + 1);
            }
        }
    }

    //isValid函数进行剪枝操作
    bool isValid(int row, int col) {
        //判断第row行，第col列能否摆放棋子，若可以拜访则返回true，否则返回false
        for (int i = 0; i < row; i++) {
            //如果处在同一列,不能摆放
            if (columns[i] == col)
                return false;
            //如果处在同一些斜线上，不能摆放
            if (row - i == col - columns[i] || -(row - i) == col - columns[i])
                return false;
        }
        return true;
    }
    void show() {
        //打印皇后摆放的位置图
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (columns[i] == j)
                    cout << "+ ";
                else
                    cout << "O ";
            }
            cout << endl;
        }
        cout << "------------------------------------------------" << endl;
    }

    int size;
    int *columns;          //第index行的皇后在column[index]列
    int way;
};

#endif /* SRC_NQUEENS_H_ */

/*
 * NQueens.h
 *
 *  Created on: 2020年3月2日
 *      Author: LuYonglei
 */

#ifndef SRC_NQUEENS_H_
#define SRC_NQUEENS_H_
#include <iostream>
using namespace std;

class Queen {
public:
    Queen(int size_) :
            size(size_ <= 0 ? 8 : size_), columns(new bool[size]), leftTop(
                    new bool[2 * size - 1]), rightTop(new bool[2 * size - 1]), queens(
                    new int[size_]), way(0) {
        int i;
        for (i = 0; i < size; i++) {
            columns[i] = false; //初始化，设置第i列没有摆放皇后
            leftTop[i] = false;
            rightTop[i] = false;
        }
        for (; i < 2 * size - 1; i++) {
            leftTop[i] = false;
            rightTop[i] = false;
        }
    }
    ~Queen() {
        delete[] columns;
        delete[] leftTop;
        delete[] rightTop;
        delete[] queens;
    }
    void placeQueens() {
        //摆放皇后
        place(0);
        cout << "共有 " << way << " 组解法。" << endl;
    }
private:
    //place进行回溯操作
    void place(int row) {
        //在第row行放置棋子
        if (row == size) {
            //如果全部摆放完成就返回
            show();
            way++;          //摆放+1
            return;
        }
        for (int col = 0; col < size; col++) {
            //如果第col列已经有皇后了
            if (columns[col])
                continue;
            //计算斜线索引
            //左上角指向右下角索引
            int ltIndex = row - col + size - 1;
            if (leftTop[ltIndex])
                continue;
            //右上角指向左下角索引
            int rtIndex = row + col;
            if (rightTop[rtIndex])
                continue;
            //可以摆放皇后
            queens[row] = col;            //记录皇后位置
            columns[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rtIndex] = true;
            place(row + 1);
            //如果产生回溯，就重置
            columns[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rtIndex] = false;
        }
    }

    void show() {
        //打印皇后摆放的位置图
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (queens[i] == j)
                    cout << "+ ";
                else
                    cout << "O ";
            }
            cout << endl;
        }
        cout << "------------------------------------------------" << endl;
    }

    int size;
    bool *columns;          //标记着某一列是否有皇后
    bool *leftTop;          //标记某一对角线是否有皇后， 斜线方向左上指向右下,共有2n-1条斜线
    bool *rightTop;          //标记某一对角线是否有皇后， 斜线方向右上指向左下，共有2n-1条斜线
    int *queens;          //皇后位置
    int way;
};

#endif /* SRC_NQUEENS_H_ */