试探回溯法（利用堆栈）

Posted on | In , | |
Words count in article: 908 | Reading time ≈ 4

试探回溯法

八皇后

国际象棋中皇后的势力范围服盖其所在的水平线、垂直线以及两条对角线。

在n x n 的棋盘上放置n个皇后，如何使得她们彼此互不攻击。

皇后

皇后是组成期盼和最终解得基本单元。

1
2
3
4
5
6
7
8
9
10
struct Queen{
    int x, y;
    Queen (int xx = 0, int yy = 0) : x (xx), y (yy) {};
    bool operator== ( Queen const& q ) const {
        return (x == q.x) || (y == q.y) || (x + y == q.x + q.y) || (x - y == q.x - q.y);
    }
    bool operator!= ( Queen const& q ) const {
        return !(*this == q);
    }
}

既然每行能且仅能放置一个皇后，故不妨首先将各皇后分配至每一行。然后，从空棋盘开始，逐个尝试着将她们放置到无冲突的某列。每放置好一个皇后，才继续试探下一个。若当前皇后在任何列都会造成冲突，则后续皇后的试探都必将是徒劳，故此时应该回溯到上一皇后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void placeQueens(int N){
    Stack<Queen> solu;
    Queen q(0,0);
    do{
        if(N <= solu.size() || N <= q.y)
        {
            q = solu.pop(); q.y++;
        }
        else
        {
            while((q.y < N) && (0 <= solu.find(q)))
            {
                q.y++; nCheck++;
            }
            if(N > q.y)
            {
                solu.push(q);
                if(N <= solu.size())  nSolu++;
                q.x++; q.y = 0;
            }
        }
    }while((0 < q.x) || (q.y < N));
}

迷宫寻径

在任意指定的起始格点与目标格点之间，找出一条通路（如果存在）

迷宫格点：

格点是迷宫的基本组成单位，首先实现Cell类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef enum {AVAILABLE, ROUTE, BACKTRACKED, WALL } Status;//迷宫单元状态
// 原始可用的，在当前路径上的，所有方向均尝试失败之后回溯过的，不可使用的（墙）

typedef enum {UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY} ESWN; //单元的相对邻接方向
// 未定、东、南、西、北、无路可通

inline ESWN nextESWN( ESWN eswn ) { return ESWN ( eswn + 1 ); } //依次转到下一邻接方向

struct Cell {
    int x, y; // x, y 坐标
    Status status; // 类型
    ESWN incoming, outgoing; //进入、走出方向
}

#define LABY_MAX 24 //最大迷宫尺寸
Cell laby[LABY_MAX][LABY_MAX]; // 迷宫

邻格查询：

1
2
3
4
5
6
7
8
9
inline Cell* neighbor ( Cell* cell ) {
    switch (Cell->outgoing){
        case EAST : return cell + LABY_MAX;
        case SOUTH: return cell + 1;
        case WEST: return cell - LABY_MAX;
        case NORTH: return cell - 1;
        default : exit (-1);
    }
}

邻格转入：

1
2
3
4
5
6
7
8
9
10
11
inline Cell* advance ( Cell* cell ) { //从当前位置转入相邻格点
    Cell* next;
    switch ( cell->outgoing ) {
       case EAST:  next = cell + LABY_MAX; next->incoming = WEST;  break; //向东
       case SOUTH: next = cell + 1;        next->incoming = NORTH; break; //向南
       case WEST:  next = cell - LABY_MAX; next->incoming = EAST;  break; //向西
       case NORTH: next = cell - 1;        next->incoming = SOUTH; break; //向北
       default : exit ( -1 );
    }
    return next;
}

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 迷宫寻径算法：在格单元s至t之间规划一条通路（如果的确存在）
bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t ) {
   if ( ( AVAILABLE != s->status ) || ( AVAILABLE != t->status ) ) return false; //退化情况
   Stack<Cell*> path; //用栈记录通路（Theseus的线绳）
   s->incoming = UNKNOWN; s->status = ROUTE; path.push ( s ); //起点
   do { //从起点出发不断试探、回溯，直到抵达终点，或者穷尽所有可能
      Cell* c = path.top(); //检查当前位置（栈顶）
      if ( c == t ) return true; //若已抵达终点，则找到了一条通路；否则，沿尚未试探的方向继续试探
      while ( NO_WAY > ( c->outgoing = nextESWN ( c->outgoing ) ) ) //逐一检查所有方向
         if ( AVAILABLE == neighbor ( c )->status ) break; //试图找到尚未试探的方向
      if ( NO_WAY <= c->outgoing ) //若所有方向都已尝试过
         { c->status = BACKTRACKED; c = path.pop(); }//则向后回溯一步
      else //否则，向前试探一步
         { path.push ( c = advance ( c ) ); c->outgoing = UNKNOWN; c->status = ROUTE; }
   } while ( !path.empty() );
   return false;
}
Donate? comment?