题目2087蓝桥杯算法提高VIP_8皇后_改 && _题目2087蓝桥杯算法提高VIP_8皇后_改

原题链接：

51. N 皇后

https://leetcode.cn/problems/n-queens/description/

题目 2087: 蓝桥杯算法提高VIP-8皇后·改
https://www.dotcpp.com/oj/problem2087.html?sid=14677565&lang=3#editor

完成情况：

解题思路：

  // TODO 先模拟出整个的棋盘，然后再进行判断即可。
    //主要是判断的时候，的注意行号，列号，以及对角线三个位置。
    //用于收集结果, 元素的index表示棋盘的row，元素的value代表棋盘的column

参考代码：

_题目2087蓝桥杯算法提高VIP_8皇后_改

package 代码随想录.回溯;

import java.util.Scanner;

public class _题目2087蓝桥杯算法提高VIP_8皇后_改 {
    //生成皇后棋盘
    private static int [][] queueChess = new int [8][8];
    //要找出最大值，那么就存在最大值比较
    private static int maxValue = Integer.MIN_VALUE;
    //用于收集结果, 元素的index表示棋盘的row，元素的value代表棋盘的column
    private static int [] chessboard = new int [8];
    /**
     * 规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
     * 找出所有满足8皇后位置的总和最大值情况的和值。
     *
     * @param args
     */
    public static void main(String[] args) {
        /*
        本题就是在找皇后的基础上，对每一种摆放位置再求一个累计和而已，本质上同皇后位置一模一样。
        //8皇后问题就是说在一个8*8的棋盘上放8个皇后，但是这8个皇后不能再同一行，同一列，同一斜线上
         */
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i <8;i++){
            for (int j = 0;j<8;j++){
                queueChess[i][j] = scanner.nextInt();
            }
        }
        backTrack(0);
        System.out.println(maxValue);
    }

    /**
     *
     * @param row
     */
    private static void backTrack(int row) {
        if (row == 8){
            countValue();
            return;
        }
        for (int i = 0; i < 8 ;i++){
            //首先尝试着把第n个皇后放在第i列上
            chessboard[row] = i;

            //判断皇后是否在同一列上，或者在同一行上
            if (inRet(row)){
                //如果不在则放下一个皇后
                backTrack(row + 1);
            }
        }
    }

    /**
     *
     * @param row
     * @return
     */
    private static boolean inRet(int row) {
        //flag[i] == flag[n]表示在不在同一列上
        //Math.abs(n - i) == Math.abs(flag[n] - flag[i])表示在不在在同一斜线上
        for (int i = 0; i < row; i++) {
            if (chessboard[i] == chessboard[row]
                    || Math.abs(row - i) == Math.abs(chessboard[row] - chessboard[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param
     */
    private static void countValue() {
        int sum = 0;
        for (int i = 0;i<8;i++){
            sum += queueChess[i][chessboard[i]];
        }
        if (maxValue < sum) maxValue = sum;
    }

}

_51N皇后_使用boolean数组表示已经占用的直or斜线

package 代码随想录.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _51N皇后_使用boolean数组表示已经占用的直or斜线 {
    List<List<String>> result = new ArrayList<List<String>>();

    boolean [] usedCol,usedDiag45,usedDiag135;
    /**
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        // TODO 先模拟出整个的棋盘，然后再进行判断即可。
        //主要是判断的时候，的注意行号，列号，以及对角线三个位置。
        //用于收集结果, 元素的index表示棋盘的row，元素的value代表棋盘的column
        int [] chessboard = new int [n];
        usedCol = new boolean[n];
        usedDiag45  = new boolean[2 * n - 1];
        usedDiag135 = new boolean[2 * n - 1];
        backTrack(n,0,chessboard);
        return result;
    }

    /**
     *
     * @param n
     * @param row   //每一行选取一个结果
     * @param chessboard
     */
    private void backTrack(int n, int row, int [] chessboard) {
        if (row == n){
            //收集结果
            List<String> listSubsets = new ArrayList<String>(); //之前的回溯是有删除链表的步骤的。
            for (int i: chessboard){
                char[] str = new char[n];
                Arrays.fill(str,'.');
                str[i] = 'Q';
                listSubsets.add(new String(str));
            }
            result.add(listSubsets);
            return;
        }
        for (int col = 0;col<n;col++){
            if (usedCol[col] | usedDiag45[row + col] | usedDiag135[row - col + n - 1]){
                continue;
            }
            chessboard[row] = col;
            // 标记该列出现过
            usedCol[col] = true;
            // 同一45°斜线上元素的row + col为定值, 且各不相同
            usedDiag45[row + col] = true;
            // 同一135°斜线上元素row - col为定值, 且各不相同
            // row - col 值有正有负, 加 n - 1 是为了对齐零点
            usedDiag135[row - col + n - 1] = true;
            // 递归
            backTrack(n,row+1,chessboard);
            //将上面的位置回溯
            usedCol[col] = false;
            usedDiag45[row + col] = false;
            usedDiag135[row - col + n - 1] = false;
        }
    }


}

错误经验吸取