描述

整數(shù) N 個(gè)皇后放在 N * N 的棋盤上，要求每個(gè)皇后不能相互攻擊，即同一行、同一列、同一斜線上不能同時(shí)存在兩個(gè)皇后，有多少種不同的方法？

分析

棋盤是個(gè)二維數(shù)組，但是每一行只有一個(gè)元素，那么可以用一維數(shù)組 board 表示棋盤, board[i] = j 表示第 i 個(gè)(行)皇后放在第 j 列上，此時(shí)再看條件

• 不能處于同一行：由于一維數(shù)組下標(biāo)表示皇后所在行，則不用考慮兩個(gè)皇后處在同一行，因?yàn)閿?shù)組下標(biāo)不可能重復(fù)；
• 不能處于同一列：對(duì)于第 i 個(gè)皇后來說，前面 i-1 個(gè)皇后均不能和第 i 個(gè)皇后所處的列相同，即 board[i] != board[0...(i - 1)];
• 不能處于同一斜線：對(duì)于第 i 個(gè)皇后，假設(shè) board[i] = a, 則對(duì)于前面 i-1 個(gè)皇后中的任意一個(gè) board[j] = b, 必須滿足 |i - j| != |a - b|

代碼

采用遞歸方式，先校驗(yàn)第 1 個(gè)皇后是否能擺放在第 1 列，如果可以則放置皇后并遞歸第 2 個(gè)皇后，否則檢驗(yàn)第 1 個(gè)皇后是否能放置在第 2 列，如果可以則放置皇后并遞歸調(diào)用第 2 個(gè)皇后，否則繼續(xù)檢驗(yàn)第 3...n 列，直到最后一個(gè)皇后放置后遞歸結(jié)束。

代碼如下

    /**
     * 返回 N 個(gè)皇后共有多少種放置方式
     * @param N
     * @return
     */
    public static int sum(int N) {
        if(N == 0) {
            return 0;
        }
        // 一維數(shù)組 board[i] = j 表示第 i 個(gè)皇后放置在第 j 列
        int[] board = new int[N];
        // 從第一個(gè)皇后開始遞歸
        return process(board, 0, N);
    }

    /**
     * 從第 row 個(gè)皇后開始擺放，返回 n 個(gè)皇后共有多少種放置方法
     * @param board
     * @param row
     * @param n
     * @return
     */
    private static int process(int[] board, int row, int n) {
        // 當(dāng)最后一行放置皇后，則返回1表示完成一種擺放方式
        // 因?yàn)槭菑?開始擺放，此時(shí)實(shí)際是滴n-1行擺放成功即可認(rèn)為完成了，下一次調(diào)用時(shí)正好加到了n
        if(row == n) {
            return 1;
        }
        int result = 0;
        for(int col=0; col<n; col++) {
            // 對(duì)于第 row 個(gè)皇后，需要檢驗(yàn)是否與前面 row - 1 個(gè)皇后是否有沖突
            if(isValid(board, row, col)) {
                // 如果沒沖突，則講皇后擺放在該位置上
                board[row] = col;
                // 進(jìn)行擺放第 row + 1 個(gè)皇后
                result += process(board, row+1, n);
            }
        }
        return result;
    }

    /**
     * 檢驗(yàn)第 row 個(gè)皇后是否可以擺放在第 col 列上
     * @param board
     * @param row
     * @param col
     * @return
     */
    private static boolean isValid(int[] board, int row, int col) {
        for(int i=0; i<row; i++) {
            if(board[i] == col || Math.abs(row - i) == Math.abs(board[i] - col)) {
                return false;
            }
        }
        return true;
    }