回溯法(一)——n皇后问题

/**
 * N皇后问题
 * @param n 矩阵规模
 * @param i 行号
 * @param result 皇后的结果集(下标表示行号，值表示列号)
 */
void NQueen( int n, int i, int[] result ){
   for( int j=0; j<n; j++ ){
        if ( canPlace(n,i,j,result) ){
            result[i] = j;
            if ( i==n-1 ) {
                printResult(result);
            }
            else {
                NQueen(n,i+1,result);
            }
        }
   } 
}

/**
 * 判断第i行第j列能不能放
 * @param n 矩阵规模
 * @param i 行号
 * @param j 列号 
 * @param result 皇后的结果集(下标表示行号，值表示列号)
 */
private boolean canPlace(int n, int i, int j, int[] result){
    for( int z=0; z<i; z++ ){
        // 判断列号是否相同、是否在对角线上（长、宽是否相等）
        if ( j==result[z] || (i-z)==Math.abs(j-result[z]) )
            return false;
    }
    return true;
}

/**
 * 打印结果集
 * @param result 结果集
 */
private void printResult(int[] result){
    for( int i=0; i<result.length; i++ ){
        System.out.println("第"+i+"行，第"+result[i]+"列"); 
    }
}