package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

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

///**
// * Problem statement: Given a N x N chess board. Return all arrangements in
// * which N queens can be placed on the board such no two queens attack each
// * other. Ex. N = 6 Solution= There are 4 possible ways Arrangement: 1 ".Q....",
// * "...Q..", ".....Q", "Q.....", "..Q...", "....Q."
// *
// * Arrangement: 2 "..Q...", ".....Q", ".Q....", "....Q.", "Q.....", "...Q.."
// *
// * Arrangement: 3 "...Q..", "Q.....", "....Q.", ".Q....", ".....Q", "..Q..."
// *
// * Arrangement: 4 "....Q.", "..Q...", "Q.....", ".....Q", "...Q..", ".Q...."
// *
// * Solution: Brute Force approach:
// *
// * Generate all possible arrangement to place N queens on N*N board. Check each
// * board if queens are placed safely. If it is safe, include arrangement in
// * solution set. Otherwise, ignore it
// *
// * Optimized solution: This can be solved using backtracking in below steps
// *
// * Start with first column and place queen on first row Try placing queen in a
// * row on second column If placing second queen in second column attacks any of
// * the previous queens, change the row in second column otherwise move to next
// * column and try to place next queen In case if there is no rows where a queen
// * can be placed such that it doesn't attack previous queens, then go back to
// * previous column and change row of previous queen. Keep doing this until last
// * queen is not placed safely. If there is no such way then return an empty list
// * as solution
// */
//public final class NQueens {
//    private NQueens() {
//    }
//
//    public static void main(String[] args) {
//        placeQueens(1);
//        placeQueens(2);
//        placeQueens(3);
//        placeQueens(4);
//        placeQueens(5);
//        placeQueens(6);
//    }
//
//    public static void placeQueens(final int queens) {
//        List<List<String>> arrangements = new ArrayList<List<String>>();
//        getSolution(queens, arrangements, new int[queens], 0);
//        if (arrangements.isEmpty()) {
//            System.out.println("There is no way to place " + queens + " queens on board of size " + queens + "x" + queens);
//        } else {
//            System.out.println("Arrangement for placing " + queens + " queens");
//        }
//        for (List<String> arrangement : arrangements) {
//            arrangement.forEach(System.out::println);
//            System.out.println();
//        }
//    }
//
//    /**
//     * This is backtracking function which tries to place queen recursively
//     *
//     * @param boardSize: size of chess board
//     * @param solutions: this holds all possible arrangements
//     * @param columns: columns[i] = rowId where queen is placed in ith column.
//     * @param columnIndex: This is the column in which queen is being placed
//     */
//    private static void getSolution(int boardSize, List<List<String>> solutions, int[] columns, int columnIndex) {
//        if (columnIndex == boardSize) {
//            // this means that all queens have been placed
//            List<String> sol = new ArrayList<String>();
//            for (int i = 0; i < boardSize; i++) {
//                StringBuilder sb = new StringBuilder();
//                for (int j = 0; j < boardSize; j++) {
//                    sb.append(j == columns[i] ? "Q" : ".");
//                }
//                sol.add(sb.toString());
//            }
//            solutions.add(sol);
//            return;
//        }
//
//        // This loop tries to place queen in a row one by one
//        for (int rowIndex = 0; rowIndex < boardSize; rowIndex++) {
//            columns[columnIndex] = rowIndex;
//            if (isPlacedCorrectly(columns, rowIndex, columnIndex)) {
//                // If queen is placed successfully at rowIndex in column=columnIndex then try
//                // placing queen in next column
//                getSolution(boardSize, solutions, columns, columnIndex + 1);
//            }
//        }
//    }
//
//    /**
//     * This function checks if queen can be placed at row = rowIndex in column =
//     * columnIndex safely
//     *
//     * @param columns: columns[i] = rowId where queen is placed in ith column.
//     * @param rowIndex: row in which queen has to be placed
//     * @param columnIndex: column in which queen is being placed
//     * @return true: if queen can be placed safely false: otherwise
//     */
//    private static boolean isPlacedCorrectly(int[] columns, int rowIndex, int columnIndex) {
//        for (int i = 0; i < columnIndex; i++) {
//            int diff = Math.abs(columns[i] - rowIndex);
//            if (diff == 0 || columnIndex - i == diff) {
//                return false;
//            }
//        }
//        return true;
//    }
//}

/**
 * 问题陈述：给定一个N x N的棋盘。返回所有可能的排列方式，
 * 使得N个皇后可以放在棋盘上而不相互攻击。例如，N = 6时，
 * 解决方案=有4种可能的方式。
 *
 * 解决方案：暴力方法：
 * 生成所有可能的排列来放置N个皇后在N*N棋盘上。检查每个
 * 棋盘是否安全放置了皇后。如果安全，则包括排列在解决方案集中。
 * 否则，忽略它。
 *
 * 优化解决方案：可以使用以下步骤的回溯法解决此问题：
 * 从第一列开始，在第一行放置皇后
 * 尝试在第二列的一行放置皇后
 * 如果放置在第二列的第二个皇后攻击任何先前的皇后，
 * 则更改第二列的行，否则移动到下一列并尝试放置下一个皇后
 * 如果没有行可以放置皇后以至于它不攻击先前的皇后，
 * 则返回到前一列并更改前一个皇后的行。
 * 继续这样做，直到最后一个皇后安全放置。
 * 如果没有这样的方法，则返回一个空列表作为解决方案。
 */
public final class NQueens {
    private NQueens() {
    }

    public static void main(String[] args) {
        // 在这里调用placeQueens方法来放置不同数量的皇后
        placeQueens(1);
        placeQueens(2);
        placeQueens(3);
        placeQueens(4);
        placeQueens(5);
        placeQueens(6);
    }

    /**
     * 放置皇后的方法
     * @param queens 皇后的数量
     */
    public static void placeQueens(final int queens) {
        List<List<String>> arrangements = new ArrayList<List<String>>();
        getSolution(queens, arrangements, new int[queens], 0);
        if (arrangements.isEmpty()) {
            System.out.println("没有办法在 " + queens + "x" + queens + " 的棋盘上放置 " + queens + " 个皇后");
        } else {
            System.out.println("放置 " + queens + " 个皇后的排列方式");
        }
        for (List<String> arrangement : arrangements) {
            arrangement.forEach(System.out::println);
            System.out.println();
        }
    }

    /**
     * 这是一个回溯函数，尝试递归地放置皇后
     * @param boardSize 棋盘大小
     * @param solutions 这保存了所有可能的排列
     * @param columns columns[i] 表示在第i列放置皇后的行号
     * @param columnIndex 正在放置皇后的列
     */
    private static void getSolution(int boardSize, List<List<String>> solutions, int[] columns, int columnIndex) {
        if (columnIndex == boardSize) {
            // 这意味着所有的皇后都已经放置
            List<String> sol = new ArrayList<String>();
            for (int i = 0; i < boardSize; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < boardSize; j++) {
                    sb.append(j == columns[i] ? "Q" : ".");
                }
                sol.add(sb.toString());
            }
            solutions.add(sol);
            return;
        }

        // 这个循环尝试逐行放置皇后
        for (int rowIndex = 0; rowIndex < boardSize; rowIndex++) {
            columns[columnIndex] = rowIndex;
            if (isPlacedCorrectly(columns, rowIndex, columnIndex)) {
                // 如果在columnIndex列的rowIndex行成功放置了皇后，则尝试在下一列放置皇后
                getSolution(boardSize, solutions, columns, columnIndex + 1);
            }
        }
    }

    /**
     * 这个函数检查皇后是否可以安全地放置在columnIndex列的rowIndex行
     * @param columns columns[i] 表示在第i列放置皇后的行号
     * @param rowIndex 要放置皇后的行
     * @param columnIndex 正在放置皇后的列
     * @return true: 如果皇后可以安全放置 false: 否则
     */
    private static boolean isPlacedCorrectly(int[] columns, int rowIndex, int columnIndex) {
        for (int i = 0; i < columnIndex; i++) {
            int diff = Math.abs(columns[i] - rowIndex);
            if (diff == 0 || columnIndex - i == diff) {
                // 如果在同一行或在对角线上，则返回false
                return false;
            }
        }
        return true;
    }
}
