回溯法–N皇后问题

@TOC

一、问题描述

1、按照国际象棋的规则，皇后可以进攻与之处在同一行或同一列或同一斜线上的棋子。
2、n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互进攻。

二、示例

2.1 四皇后的2个可行解

2.2 过程图示

以四皇后为例，展示寻找一种可行解的过程

三、问题分析

3.1涉及到的概念

递归

自己调自己,在方法中调用方法本身。
使用递归需要注意：
1、递归要有出口，不能是死循环，死循环会造成栈溢出。
2、递归次数不宜过多，过多也会有栈溢出的问题。

回溯

回溯法是一种解决问题的算法，它会尝试每一种可能的解决方案来找到最佳解。

3.2 分析

回溯法一般通过递归实现。在n皇后问题中，我们可以从第一行开始，每行放置皇后，检查该皇后是否与之前的皇后冲突，如果没有则放置下一行的皇后，如果发现无解则回溯到上一行重新尝试。

回溯用递归的方式去控制for嵌套的层数，4×4递归4层，每一层有一个for循环，遍历每一层对应的位置。时间复杂度和嵌套for循环一致。

四、 代码实现

4.1 实现思路

宏观：

使用深度搜索的方法，按照先行后列的顺序，查看每一个位置是否满足条件。

微观：

1. 定义二维数组表示棋盘，定义一个变量n表示几个皇后
2. 定义一个方法用来判断当前摆放的皇后是否与之前的皇后冲突（同列、左上方，右上方)，冲突返回0；否则，返回1，表示此位置可以放置皇后。
3. 定义一个递归函数，尝试在当前行放置皇后。

这里给一个回溯代码模板

if(终止条件){
    收集结果；
    return;
}

for(遍历本层集合中的元素){
    处理节点；
    递归；
    回溯，撤销处理结果
}

4.2 递归函数NS图

4.3 代码

package com.lsn.NQueen;

public class NQueens {

    // 定义一个二维数组表示棋盘
    int[][] board;

    // 定义一个变量表示几个皇后
    int n;

    // 构造函数，初始化棋盘和n
    public NQueens(int n) {
        board = new int[n][n];
        this.n = n;
    }

    // 判断当前摆放的皇后是否与之前的皇后冲突
    public boolean isSafe(int row, int col) {
        int i, j;

        // 检查当前列是否有皇后
        for (i = 0; i = 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        // 检查右上方是否有皇后
        for (i = row, j = col; i >= 0 && j 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: solidity教学–快速入门

智能合约 一个存储的例子 // SPDX-License-Identifier: GPL-3.0 pragma solidity >=0.4.16 第一行告诉您源代码是在 GPL 3.0 版下获得许可的。机器可读的许可证说明符在默认发布源代码的设置中非常…