回溯算法

1、八皇后问题
我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线
都不能有另一个棋子。你可以看我画的图，第一幅图是满足条件的一种方法，第二幅图是不
满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。

2、解答

/**
 * 回溯算法-八皇后问题
 */
public class NQueen {

    int[] res = new int[4];

    public static void main(String[] args) {
        new NQueen().cal8Queens(0);
    }

    public void cal8Queens(int row) {
        if (row == 4) {
            printRes(res);
            return;
        }

        for (int col = 0; col < 4; col++) {
            if (isOk(row, col)) {
                res[row] = col;
                cal8Queens(row  +1);
            }
        }

    }

    private void printRes(int[] res) {
        for (int row = 0; row < 4; row++) {
            for (int col = 0; col < 4; col++) {
                if (res[row] == col) {
                    System.out.print("Q");
                } else {
                    System.out.print("*");
                }
            }
            System.out.println();
        }
        System.out.println();

    }

    private boolean isOk(int row, int col) {
        //左上角
        int leftUp = col - 1;
        // 右上角
        int rightUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            // 当前点上有，返回false
            if (res[i] == col) {
                return false;
            }
            // 左上角或右上角有
            if (leftUp >= 0) {
                if (res[i] == leftUp) {
                    return false;
                }
            }
            if (rightUp < 4) {
                if (res[i] == rightUp) {
                    return false;
                }
            }

            leftUp--;
            rightUp++;
        }

        return true;
    }

}