算法描述

• 试探回溯算法
  • 试探
    • 从零开始，尝试逐步增加候选解的长度(本质上是成批的考察具有特定前缀的所有候选解),这种从长度上逐渐向目标解靠近的尝试叫做试探
  • 回溯
    • 一般问题候选解都是呈树状分布的，某个节点不合法，则舍弃这个分支，然后回溯到上上个节点，探索其他的可能

八皇后的问题

算法实现

• 依赖栈实现

// 定义女皇结构
struct Queen {
    int x, y; // x,y坐标
    Queen(int xx=0, int yy=0) : x(xx), y(yy) {};

    // 重载==运算符
    bool operator==(Queen const &q) {
        return (x == q.x) // 行冲突
               || (y == q.y) //列冲突
               || (x + y == q.x + q.y) //沿对角线冲突
               || (x - y == q.x - q.y);

    }

    // 重载 !=运算符
    bool operator!=(Queen const &q) {
        return !(*this == q);
    }
};


// 试探回溯法获取N皇后算法
// 国际象棋要求每行只可能出现一个皇后，所以每行的皇后都在(N,0)为远点,不断的移动列，如果当前行越界，则回溯到上一行
 void placeQueens(int N) {
    // N必需大于1
    if (N < 2) {
        throw "N必需大于1";
    }

    // 栈存放部分皇后信息
    Stack<Queen> solu;

    // 原点皇后
    Queen queen(0, 0);
    do {
        // 如果越界, 则回溯到上一行,并试探下一列
        if (queen.y >= N) {
            queen = solu.pop();
            queen.y++;
        } else {
            // 如果栈中皇后和当前queen冲突 则继续移动queen列
            while (solu.find(queen) && queen.y < N) {
                queen.y++;
            }

            // 如果当前queen没有越界 则入栈
            if (queen.y <N) {
                solu.push(queen);

                // 如果找到了全部解 则中断循环
                if (solu.size() >= N) {
                    break;
                }

                // 否则继续下一行的第一列
                queen.x++;
                queen.y = 0;
            }
        }

        // 回溯到(0,N-1)之前都是合法的
    } while (queen.x > 0 || queen.y < N);

    // 打印皇后在的位置
    solu.traverse(printItem);
}

可执行脚本

• main

#include "iostream"
#include "string"
#include "Stack.h"

using namespace std;

// 打印皇后在的位置
template<typename T> void printItem(T queen)
{
    static int number = 1;

    cout <<"第" << number << "个皇后 " << "queen.x=" << queen.x << " queen.y=" << queen.y << endl;
    number ++;
}

// 试探回溯法获取N皇后算法
// 国际象棋要求每行只可能出现一个皇后，所以每行的皇后都在(N,0)为远点,不断的移动列，如果当前行越界，则回溯到上一行
 void placeQueens(int N) {
    // N必需大于1
    if (N < 2) {
        throw "N必需大于1";
    }

    // 栈存放部分皇后信息
    Stack<Queen> solu;

    // 原点皇后
    Queen queen(0, 0);
    do {
        // 如果越界, 则回溯到上一行,并试探下一列
        if (queen.y >= N) {
            queen = solu.pop();
            queen.y++;
        } else {
            // 如果栈中皇后和当前queen冲突 则继续移动queen列
            while (solu.find(queen) && queen.y < N) {
                queen.y++;
            }

            // 如果当前queen没有越界 则入栈
            if (queen.y <N) {
                solu.push(queen);

                // 如果找到了全部解 则中断循环
                if (solu.size() >= N) {
                    break;
                }

                // 否则继续下一行的第一列
                queen.x++;
                queen.y = 0;
            }
        }

        // 回溯到(0,N-1)之前都是合法的
    } while (queen.x > 0 || queen.y < N);

    // 打印皇后在的位置
    solu.traverse(printItem);
}


int main() {
    placeQueens(8);
    return 0;
}

• 女皇结构 Queen.h

// 定义女皇结构
struct Queen {
    int x, y; // x,y坐标
    Queen(int xx=0, int yy=0) : x(xx), y(yy) {};

    // 重载==运算符
    bool operator==(Queen const &q) {
        return (x == q.x) // 行冲突
               || (y == q.y) //列冲突
               || (x + y == q.x + q.y) //沿对角线冲突
               || (x - y == q.x - q.y);

    }

    // 重载 !=运算符
    bool operator!=(Queen const &q) {
        return !(*this == q);
    }
};

• 栈结构 Stack.h

#include "Queen.h"
#include "listNode.h"
#include "list.h"

// 栈的实现
template<typename T>
class Stack : public List<T> {
public :
    // push 入栈
    void push(T data) {
        this->insertAsLast(data);
    }

    // pop 出栈
    T pop() {
        return this->remove(this->last());
    }

    //  top 取栈顶
    T &top() {
        return this->last()->data;
    }
};

• 列表节点结构 listNode.h

using namespace std;
#define ListNodePosi(T) ListNode<T>*

typedef int Rank;
typedef int RANK;

template<typename T>
struct ListNode {
    T data;
    ListNodePosi(T) pred; // 前缀
    ListNodePosi(T) succ; // 后继

    // 构造函数
    ListNode(){};

    // 带参数的构造函数
    ListNode(T e, ListNodePosi(T) p = NULL, ListNodePosi(T) s =NULL) : data(e), pred(p), succ(s) {};

    // 前插入
    ListNodePosi(T) insertAsPred(T const&e);

    // 后插入
    ListNodePosi(T) insertAsSucc(T const&e);
};

template<typename T> ListNodePosi(T)   ListNode<T>::insertAsPred(T const& e){
// 插入新增的节点
    ListNodePosi(T) new_node = new ListNode(e, pred, this);
// 新节点进入连接
    pred->succ = new_node;
    pred = new_node;
    return new_node;
};

// 插入当前节点后面
template<typename T> ListNodePosi(T)  ListNode<T>::insertAsSucc(T const& e){
// 新节点
    ListNodePosi(T) new_node = new ListNode(e, this, succ);

// 当前节点的原后缀节点的前缀节点改成新节点
    succ->pred = new_node;

// 当前节点的后缀节点改成
    succ = new_node;
    return new_node;
};

• 列表结构 list.h

using namespace std;

#define STATUS_ERROR -1
//typedef  Queen T;

template<typename T>
class List {
private:
    // 规模
    int _size;

    // 头节点
    ListNodePosi(T) header;

    // 尾指针
    ListNodePosi(T) trailer;

protected:
    // 列表创建时初始化
    void init();

    // 清除所有节点
    int clear();

    // 复制列表中自位置p起的n项
    void copyNodes(ListNodePosi(T) p,int n);

public:
    // 构造方法
    List() { init(); };

    // 析构方法
    ~List(){
        clear();
        delete trailer;
        delete header;
    };//释放所有节点

    // 获取规模
    Rank size() { return _size; };

    // 列表是否为空
    bool empty() { return _size < 1; }

    // 重载[]
    T& operator[](Rank r);

    // 获取首节点
    ListNodePosi(T) const first() {
        return header->succ;
    }

    // 获取末节点
    ListNodePosi(T) const last() {
        return trailer->pred;
    }

    // 某个节点是否合法
    bool valid(ListNodePosi(T) p) {
        // 节点不为空并且不是头尾节点
        return p && p != trailer && p != header;
    }

    // 插入首节点
    ListNodePosi(T) insertAsFirst(T const& e){
      _size ++;
      return header->insertAsSucc(e);
    };

    // 插入尾节点
    ListNodePosi(T) insertAsLast(T const& e);

    // 将e当作节点p的后继插入
    ListNodePosi(T) insertA(ListNodePosi(T) p, T const& e);

    // 将e当作节点p的前驱插入
    ListNodePosi(T) insertB(ListNodePosi(T) p, T const& e);

    // 删除特定的节点，返回特定的元素
    T remove(ListNodePosi(T) p);

    // 遍历 函数指针机制遍历
    void traverse(void (*)(T&));

    // 无序去重
    int deduplicate();

    // 无序列表中查找(全局)
    ListNodePosi(T) find(T const &e){
        return find(e, _size, trailer);
    }

    // 无序列表中查找  没有找到返回NULL
    ListNodePosi(T) find(T const &e, int n , ListNodePosi(T) p);

    // 有序列表内节点p的个前驱元素中找到不大于e的最后一个元素
    ListNodePosi(T) search(T const &e, int n , ListNodePosi(T) p);

    // 插入排序
    void insertionSort(ListNodePosi(T) p,int n);

    // 选择排序
    void selectionSort(ListNodePosi(T) p,int n);

    // 从启始于p元素的n个节点中选取最大节点
    ListNodePosi(T) selectMax(ListNodePosi(T) p, int n);
};

// 从启始于p元素的n个节点中选取最大节点 （rank(p), n+ rank(p)) 不包含
template <typename T> ListNodePosi(T) List<T>::selectMax(ListNodePosi(T) p, int n){
    // 设置默认的最大节点
    ListNodePosi(T) node_max = p;

    // 当前循环的节点
    ListNodePosi(T) node_current = p;

    while(n-- >= 0){
        // 当前节点如果大于最大节点 则替换
        if (node_current->data > node_max->data) {
            node_max = node_current;
        }

        // 进入下一次循环
        node_current = node_current->succ;
    }
    return node_max;
}

// 选择排序 无序的前缀和有序的后继,每次从无序的前缀中选择最大的值填充为后继的首元素
template <typename T> void List<T>::selectionSort(ListNodePosi (T) p, int n) {
    // p节点是否有效
    if (!valid(p)) {
        throw STATUS_ERROR;
    }

    // 设置开始无序前缀的开始节点和结束节点 (当前节点的前一个作为锚点)
    ListNodePosi(T) head = p->pred;

    // 设置开始无序前缀的结束节点
    ListNodePosi(T) tail = p;
    for (int i = 1; i <n ; ++i) {
        tail = tail->succ;
        if (tail == NULL) {
            throw "p节点之后没有";
        }
    }

    // 本次循环值最大的节点和新生成的节点
    ListNodePosi(T) current_max;
    ListNodePosi(T) node_new;

    // 第一次缓存
    int first_loop = n -1;
    while (n-- > 1) { // 如果只剩下一个节点 则没有排序的意义

        // 获取本次循环中值最大得节点
        current_max = selectMax(head->succ, n);

        // 将最大值节点插入后继有序序列的首元素
        // 第一次插入尾元素的下一个, 以后插入新元素的前一个
        if (n == first_loop) {
            node_new = insertA(tail, current_max->data);
        } else {
            node_new = insertB(node_new, current_max->data);
        }

        // 删除最大节点
        remove(current_max);
    }
}

// 有序列表内节点p的个前驱元素中找到不大于e的最后一个元素
template <typename T> ListNodePosi(T) List<T>::search(T const &e, int n , ListNodePosi(T) p){
    // p可能是trailer
    // 0 <= n <= rank(p) < _size;
    if (n < 0 || n > _size) {
        throw STATUS_ERROR;
    }

    while(n-- >= 0) {
        p = p->pred;
        if (p->data <= e) {
            break;
        }
    }
    return p;
}

// 插入排序: 对于起始于节点p的n个节点进行排序（包含N）    将序列分成有序的前缀和无序的后缀， 反复的将无序后缀的首元素插入到前缀合适的位置
template <typename T> void List<T>::insertionSort(ListNodePosi (T) p, int n) {
    // p必需是合法的节点 && rank(p) + n <+ _size
    if (!valid(p)) {
        cout << "不合法的节点p" << endl;
        throw STATUS_ERROR;
    }
    ListNodePosi (T) node_small;
    for(int i = 0; i< n; i ++) {
        // 有序前缀中不大于无序后继首元素的最后一个节点
         node_small = search(p->data, i, p);

        // 首元素插入前缀有序列表
        insertA(node_small, p->data);

        // 更新循环依据
        p = p->succ;

        // 元素后继的首元素
       remove(p->pred);
    }
}

// 无序列表中查找, 在节点p的n个前驱元素中查数据e, 并返回逻辑次序最大的节点
template <typename T>
ListNodePosi(T) List<T>::find(T const &e, int n , ListNodePosi(T) p){
    // 如果n 异常
    if (n < 0  || n > _size) {
        return NULL;
    }

    // 另外rank(p) >= n
    while(n-- > 0) {

        // 循环直到n个结束
        p = p->pred;

        // 如果p节点之前没有n个节点， 则抛出异常
        if (p == header) {
            throw STATUS_ERROR;
        }

        if (p->data == e) {
            return p;
        }
    }

    return NULL;
}

// 无序列表去重
template <typename T> int List<T>::deduplicate()
{
    // 平凡列表自然无重复
    if (_size < 2) {
        return 0;
    }

    int old_size = _size;

     // 从第二个元素开始每个元素都要和逻辑次序在它之前的节点进行比较
     // 循环节点
    ListNodePosi(T) p = first();
    RANK r = 1;
    while((p = p->succ) != trailer) {

        // p节点之前是否存在这个数据
        ListNodePosi(T) exist_node = find(p->data, r, p);
        exist_node ? remove(exist_node) : r ++;
    }

    return old_size - _size;
}


// 借助函数指针
template <typename T> void List<T>::traverse(void (*visit)(T &)) {
    for (ListNodePosi(T) p = header->succ; p != trailer ; p = p->succ) {
        visit(p->data);
    }
}

// 删除特定的节点，返回特定的元素
template <typename T> T List<T>::remove(ListNodePosi(T) p) {
    // 备份待删除节点
    T data = p->data;

    // 当前页面的上一个节点的后继节点改成p的后继节点
    p->pred->succ = p->succ;

    // p的后继节点改成p的前驱节点
    p->succ->pred = p->pred;

    delete p;

    // 规模减1
    _size --;
    return data;
}

// 清理掉所有的数据节点,并返回原有节点的数量
template <typename T> int List<T>::clear(){
    int old_size = _size;

    // 反复删除首节点，直到列表数据为空
    while (_size > 0) {
        remove(first());
    }

    return old_size;
}

// 插入尾节点
template <typename T>
ListNodePosi(T) List<T>::insertAsLast(T const& e){
    _size ++;
    return trailer->insertAsPred(e);
}

// 将e当作节点p的后继插入
template <typename T>
ListNodePosi(T) List<T>::insertA(ListNodePosi(T) p, T const& e){
    _size ++;
    return p->insertAsSucc(e);
}

// 将e当作节点p的前驱插入
template <typename T>
ListNodePosi(T) List<T>::insertB(ListNodePosi(T) p, T const& e){
    // 生成一个新的节点
    _size ++;
    return p->insertAsPred(e);
}


// 重载[]
template<typename T>
T& List<T>::operator[](Rank r) {
    if (r < 0 || r > _size) {
        return -1;
    }

    // 首节点
    ListNodePosi(T) p = first();

    for (int i = 1; i < r; ++i) {
        p = p->succ;
    }
    return p->data;
}

// 初始化列表函数
template<typename T>
void List<T>::init() {
    // 生成头节点
    header = new ListNode<T>;

    // 生成尾节点
    trailer =new  ListNode<T>;

    // 生成头尾节点的联系
    header->succ = trailer;
    trailer->pred = header;

    header->pred = NULL;
    trailer->succ = NULL;

    // 规模初始化0
    _size = 0;
}