用回溯法求解N皇后和迷宫问题

关于回溯法不再赘述太多，大家移步各种百科，本文介绍两种应用的实现

其典型应用之一： N皇后问题

按皇后摆放规则顺序遍历棋盘依次安放皇后，直到某一个皇后找不到合适的位置时，倒退至上一步，调整上一个皇后位置，如还不满足，继续调整再上一个，依次类推。

上述过程很容易想到用栈实现，其一组特解的代码如下

void search_solution()
{
	struct position tmp;
	int i = 0, j = 0;
	for (; i < N; )
	{
		for (; j < N; j++)
		{
			if (detect(i,j))
			{
				map[i][j] = 1;
				push(i,j);
				break;
			}
		}
		if (j == N)
		{
			tmp = pop();
			i = tmp.i;
			j = tmp.j;
			map[i][j] = 0;
			j++;
		}
		else
		{
			i++;
			j = 0;
		}
	}
}

void search_all_solution()
{
	struct position tmp;
	int i = 0, j = 0;
	while (1)
	{
		for (; i < N; )
		{
			for (; j < N; j++)
			{
				if (detect(i,j))
				{
					map[i][j] = 1;
					push(i,j);
					break;
				}
			}
			if (j == N)
			{
				tmp = pop();
				i = tmp.i;
				j = tmp.j;
				map[i][j] = 0;
				j++;
			}
			else
			{
				i++;
				j = 0;
			}
		}
		if (i == N)
		{
			count++;
			print_solution();
			tmp = pop();
			i = tmp.i;
			j = tmp.j;
			map[i][j] = 0;
			j++;

		}
	}
}

#include
  
   
#include
   
     #define N 8 #define MAX_STACK_SIZE 64 struct position { int i, j; }; int map[N][N]; int empty_flag = 0; int top = -1; int count = 0; struct position stack[MAX_STACK_SIZE]; void push(int i, int j) { top++; stack[top].i = i; stack[top].j = j; empty_flag = 0; } struct position pop() { if (top == -1) { printf("%d solutions\n", count); exit(0); printf("stack is empty!\n"); empty_flag = 1; } return stack[top--]; } void print_solution() { int i, j; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) printf("%2d", map[i][j]); printf("\n"); } printf("\n"); } int detect(int row, int col) { int i = row, j; for (j = 0; j < N; j++) if (map[i][j]) return 0; j = col; for (i = 0; i < N; i++) if (map[i][j]) return 0; i = row; while (++i < N && ++j < N) { if (map[i][j]) return 0; } i = row; j = col; while (--i >= 0 && --j >= 0) { if (map[i][j]) return 0; } i = row; j = col; while (++i < N && --j >= 0) { if (map[i][j]) return 0; } i = row; j = col; while (--i >= 0 && ++j < N) { if (map[i][j]) return 0; } return 1; } void search_solution() { struct position tmp; int i = 0, j = 0; for (; i < N; ) { for (; j < N; j++) { if (detect(i,j)) { map[i][j] = 1; push(i,j); break; } } if (j == N) { tmp = pop(); i = tmp.i; j = tmp.j; map[i][j] = 0; j++; } else { i++; j = 0; } } } void search_all_solution() { struct position tmp; int i = 0, j = 0; while (1) { for (; i < N; ) { for (; j < N; j++) { if (detect(i,j)) { map[i][j] = 1; push(i,j); break; } } if (j == N) { tmp = pop(); i = tmp.i; j = tmp.j; map[i][j] = 0; j++; } else { i++; j = 0; } } if (i == N) { count++; print_solution(); tmp = pop(); i = tmp.i; j = tmp.j; map[i][j] = 0; j++; } } } int main() { memset(map, 0, sizeof(map)); // search_solution(); // print_solution(); search_all_solution(); printf("%d solutions\n", count); return 0; }
   
  

遇到分岔路口就把分岔的坐标入栈，沿着其中一条走下去，如果无解返回分岔坐标，如此类推：

解释下程序中的矩阵，0表示路，1表示墙，走过的路径用8表示。每走一步打印一次地图可观察到程序的执行情况

#include
  
   
#include
   
     #define ROW 7 #define COL 7 #define MAX_STACK_SIZE 32 #define UP 0 #define RIGHT 1 #define DOWN 2 #define LEFT 3 int maze[ROW][COL] = { 0,1,0,0,0,1,0, 0,1,1,1,0,0,0, 0,0,0,1,0,1,0, 0,1,1,1,0,1,1, 0,0,0,1,0,0,0, 0,1,0,1,0,1,0, 0,0,0,0,0,1,0, }; typedef struct Point_tag { int row, col; }Point; Point stack[MAX_STACK_SIZE]; int top = -1; int direction[4] = {0, 0, 0, 0}; //从第一个元素开始，依次标识上（0），右（1），下(2)，左(3), 表示方向貌似有更好的方法 void push(Point po) { if (top == MAX_STACK_SIZE - 1) printf("stack is full!\n"); else stack[++top] = po; } Point pop() { if (top == -1) printf("stack is empty!\n"); else return stack[top--]; } void print_maze() { int i, j; for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) printf("%2d", maze[i][j]); printf("\n"); } printf("\n"); } void count_direction(Point po, int current_dir) { if (po.row + 1 < ROW && maze[po.row+1][po.col] != 1 && maze[po.row+1][po.col] != 8 /*&& current_dir != UP*/) direction[DOWN] = 1; if (po.col + 1 < COL && maze[po.row][po.col+1] != 1 && maze[po.row][po.col+1] != 8 ) direction[RIGHT] = 1; if (po.row - 1 >= 0 && maze[po.row-1][po.col] != 1 && maze[po.row-1][po.col] != 8) direction[UP] = 1; if (po.col - 1 >= 0 && maze[po.row][po.col-1] != 1 && maze[po.row][po.col-1] != 8) direction[LEFT] = 1; } int num_of_dir() { int i = 0, count = 0; for (; i < 4; i++) if (direction[i] == 1) count++; return count; } int local_dir() { int i = 0; for (; i < 4; i++) if (direction[i] == 1) return i; } void search(Point head , int cur_dir) { int numofdir, next_dir = 0, dir = cur_dir; while (1) { maze[head.row][head.col] = 8; count_direction(head, dir); numofdir = num_of_dir(); if (numofdir == 0) head = pop(); else { if (numofdir > 1) push(head); next_dir = local_dir(); switch (next_dir) { case UP: { head.row--; break; } case RIGHT: { head.col++; /*dir = RIGHT;*/ break; } case DOWN: { head.row++; break; } case LEFT: { head.col--; break; } } } memset(direction, 0, sizeof(int) * 4); print_maze(); if (head.row == ROW - 1 && head.col == COL - 1) { maze[head.row][head.col] = 8; print_maze(); printf("success to escape!\n"); break; } } } int main() { Point Head = {0, 0}; int dir = 2; search(Head, dir); return 0; }