N皇后——解决方案（Java、C实现过程）

      Hello,大家好，我是带风的pose哥,面对残酷生活的镜头，也不要忘了摆pose呀！

问题描述

温馨提示：下面我会以n=4作为示例讨论算法实现过程，小伙伴们可自行改动！

游戏规则          在编写程序之前，我们当然要先很好地理解N皇后游戏规则并总结其规律，如果已经熟悉的可以跳过这部分哦！
        N皇后由n×n的大小棋盘构成，棋子之间不能互相攻击，当很多人读到“不能互相攻击“时总是会片面地认为临近即攻击，其实不是的，N皇后也可实现“隔空攻击”。 总结来说每下一个棋子，该棋子的位置不能在与之前下的棋子的行、列、主对角线和副对角线上。

Java程序实现

import java.util.*;
public class N_queen {
	static int x = 0;
	static List<List<String>> res = new ArrayList<List<String>>();
	static int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};   //上、下、左、右、左上、左下、右上、右下
	static int[] dy = {0, 0, -1, 1, -1, -1, 1, 1};	 //上、下、左、右、左上、左下、右上、右下
	public static void main(String[] args) {
	     int n = 4;
		 int[][] chess = new int[n][n];  //布置棋盘，元素为0代表该元素的位置可以下棋，非0代表不可以下棋
		 StringBuilder reflect = new StringBuilder(); 
         Deque<String> deque = new ArrayDeque<String>(); //栈结构存储棋子所在行对应字符串
         for(int i = 0; i < n; i++){  //初始化棋盘空行
             reflect.append('.');
         }
	        dfs(0,chess,deque,reflect,n);
	}
	
	static void dfs(int x,int[][] chess, Deque<String> deque,StringBuilder reflect,int n){
        if(x == n ){
        	res.add(new ArrayList<String>(deque));
        	System.out.println(deque.toString());
            return;
        }
        else{
            for(int y = 0; y < n; y++){  
                if(chess[x][y] == 0){
                    update(x, y, chess, n, true);
                    reflect.setCharAt(y, 'Q'); 
                    deque.addLast(reflect.toString()); //入栈当前棋盘一行中棋子的分布
                    reflect.setCharAt(y, '.');
                    dfs(x+1,chess,deque,reflect,n);
                    deque.removeLast();  //出栈
                    update(x, y, chess, n, false);
                }
                else{
                    if(y == n - 1) return;
                }
            }
        }
        return;
    }
	
	static void update(int x, int y, int[][] chess, int n, boolean flag){ //更新棋盘，flag值为true代表前进，false代表返回上一步棋盘的状态
		if(flag) {
			chess[x][y] += 1;
		}else {
			chess[x][y] -= 1;
		}
		int xx;
		int yy;
	    for(int i = 0; i < 8; i++) {
	    	xx = x + dx[i];
			yy = y + dy[i];
	    	while(xx >= 0 && xx < n && yy >= 0 && yy < n) {
	    		if(flag) {
	    			chess[xx][yy] += 1;
	    		}else {
	    			chess[xx][yy] -= 1;
				}
	    		xx += dx[i];
	    		yy += dy[i];
	    	}
	    }
	  }
}

C语言程序实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 4
typedef struct stack{
	char idea[n][n+1]; //存放棋盘中多行的字符串，整体为一种N皇后的解决方案  
	int top;   //初始化栈顶
}Stack;

void show(Stack *stack);  //（输出栈中的二维数组） 
void update(int x, int y, int chess[n][n], int flag);  //更新棋盘 
void dfs(int x, int chess[n][n], Stack *stack, char reflect[]);  //深度优先搜索函数 

static int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1};   //上、下、左、右、左上、左下、右上、右下
static int dy[] = {0, 0, -1, 1, -1, -1, 1, 1};	 //上、下、左、右、左上、左下、右上、右下

int main()
{
	int chess[n][n] = {{0},{0}}, i;  //初始化棋盘chess数组 
	char reflect[n];
	for(i = 0; i < n; i++){  //初始化棋盘中一行的字符串表示 
		reflect[i] = '.';
	}
	Stack *stack = (Stack *) malloc (sizeof(Stack));  //分配结构体指针内存 
	stack->top = -1;  //初始化栈顶，-1代表当前栈为空 
	dfs(0,chess,stack,reflect);
	return 0;
  }
void show(Stack *stack){
	int i;
	printf("\n");
	for(i = 0; i < n; i++){
		printf("%s   ",stack->idea[i]);
	}
}
void update(int x, int y, int chess[n][n], int flag){ //更新棋盘，flag值为true代表前进，false代表返回上一步棋盘的状态
		if(flag) {
			chess[x][y] += 1;
		}else {
			chess[x][y] -= 1;
		}
		int i, xx, yy;
	    for(i = 0; i < 8; i++) {
	    	xx = x + dx[i]; 
			yy = y + dy[i];
	    	while(xx >= 0 && xx < n && yy >= 0 && yy < n) {  //对应dx,dy所代表的方向前进，直到超出棋盘大小就停止 
	    		if(flag) {
	    			chess[xx][yy] += 1;
	    		}else {
	    			chess[xx][yy] -= 1;
				}
	    		xx += dx[i];
	    		yy += dy[i];
	    	}
	    }
	    
	  }
void dfs(int x, int chess[n][n], Stack *stack, char reflect[]){
	if(x == n){
		show(stack);
		return;
	}
	else{
		int y;
		for(y = 0; y < n; y++){
			if(chess[x][y] == 0){
				update(x, y, chess, 1);
				reflect[y] = 'Q';
   			    strcpy(stack->idea[++stack->top],reflect);  //设置当前栈顶元素字符串 
   			    reflect[y] = '.';
   			    dfs(x+1, chess, stack, reflect);
    			strcpy(stack->idea[stack->top--],""); //设当前栈顶元素字符串为空，返回上一步操作 
    			update(x, y, chess, 0);
			}else{
				if(y == n - 1) return;
			}
		}
	}
}

算法模拟      在这里我根据程序的运行顺序，实时模拟棋盘数组中元素的变化（包括回溯后），让大家更加直观理解回溯算法模型。↓ ↓ ↓（当然我只是模拟了前面的几步，大家理解后可以尝试自己去画出后面的几步!）

难点分析与设计

• 更新棋盘
           我们将棋子的位置用(x,y)坐标表示，那么如何快速表示出该棋子的行、列、主对角线、副对角线不能再下棋呢？我们知道每下一颗棋后更新可能与上一次更新棋盘有重叠部分，如何设计回溯的时候不会直接清除重叠部分，而是类似一种“缓解”限制范围的一种效果呢？
           面对第一个问题：我设计了dx,dy数组表示横、纵坐标对应上、下、左、右、左上、左下、右上、右下八个方向的变化.
  static int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1}; //上、下、左、右、左上、左下、右上、右下
  static int dy[] = {0, 0, -1, 1, -1, -1, 1, 1}; //上、下、左、右、左上、左下、右上、右下
          面对第二个问题：调用update函数，定义两个局部变量(int xx = x + dx[i] ,int yy = y + dy[i])来表示当对应方向横、纵坐标的变化，并且在chess数组棋盘中将(xx,yy)对应元素的值+1或-1，当xx、yy超出chess数组的范围，则while循环结束，当前方向的循环结束，进入下次循环。
• 预存结果、死局破解
      大家直接看图吧，可以直观感受到栈结构发生的变化
  

运行效率（以java代码示例）

         感谢大家的耐心观看，如果您对该博客喜欢或者帮助到您，我就很开心啦！欢迎点赞、收藏、评论三连招，如有不足，欢迎指正提出！感谢您的支持。
                                                               ----带风的pose哥