深度優先算法練習

提示：文章寫完後，目錄可以自動生成，如何生成可參考右邊的幫助文檔

BM59 N皇後問題

• 題目描述
• 一、思路引出
• 二、算法設計
• • 1.Java代碼
  • 2、效率分析
• 總結

題目描述

N 皇後問題是指在 n * n 的棋盤上要擺 n 個皇後，

要求：任何兩個皇後不同行，不同列也不在同一條斜線上，

求給一個整數 n ，傳回 n 皇後的擺法數。

資料範圍: 1<=n<=9，1≤n≤9

要求：空間複雜度 O(1) ，時間複雜度 O(n!)

一、思路引出

n皇後問題屬于典型的深度優先思想算法設計題，一般是依次周遊所有行，在每行内周遊尋找所有不沖突的可擺放列，找到該行一個不沖突的列，遞歸到下一行繼續尋找不沖突的列，直到遞歸至最後一行找到一種可能的擺放方式

二、算法設計

1.Java代碼

①遞歸子產品

//深度優先搜尋可能的擺放方式
    public void search(int row, int n){
        //周遊目前行(第row行)的全部列，找到該行所有不沖突的可選擇的擺放位置
        for(int col=1; col<=n; col++){
            //按順序先擺放一個皇後,之後調用place方法判斷放置在該位置是否會造成沖突
            queen[row] = col;
            if(place(row) && row<=n){
                if(row==n){
                    put_ways++;//不沖突且該行已為最後一行，則說明找到了一種新的擺放方式
                }else{
                    search(row+1, n);//不沖突則遞歸去下一行尋找不沖突的擺放位置
                } 
            }//周遊目前行所有列并完成之後行的遞歸後，程式将回溯至上一行
        }
    }
           

②沖突判斷

//判斷剛剛放置在第row行的皇後是否會和之前行的皇後發生沖突
    public boolean place(int row){
        for(int last_row=1; last_row<row; last_row++){
            //分别判斷是否存在縱向沖突和斜向沖突
            if(queen[last_row]==queen[row] || Math.abs(queen[last_row]-queen[row])==row-last_row){
                return false;
            }
        }
        return true;
    }
           

③完整代碼

import java.util.*;
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    private int put_ways;//累加計算擺放方式
    private int[] queen;//queen數組依次存儲1-n行各行的擺放列号
        
    public Solution(){
        this.put_ways = 0;
    }
    
    public int Nqueen (int n) {
        if(n<=0){
            return 0;
        }
        
        queen = new int[n+1];
        search(1, n);
        return put_ways;
    }
    
    //深度優先搜尋可能的擺放方式
    public void search(int row, int n){
        //周遊目前行(第row行)的全部列，找到該行所有不沖突的可選擇的擺放位置
        for(int col=1; col<=n; col++){
            //按順序先擺放一個皇後,之後調用place方法判斷放置在該位置是否會造成沖突
            queen[row] = col;
            if(place(row) && row<=n){
                if(row==n){
                    put_ways++;//不沖突且該行已為最後一行，則說明找到了一種新的擺放方式
                }else{
                    search(row+1, n);//不沖突則遞歸去下一行尋找不沖突的擺放位置
                } 
            }
        }
    }
    
    //判斷剛剛放置在第row行的皇後是否會和之前行的皇後發生沖突
    public boolean place(int row){
        for(int last_row=1; last_row<row; last_row++){
            //分别判斷是否存在縱向沖突和斜向沖突
            if(queen[last_row]==queen[row] || Math.abs(queen[last_row]-queen[row])==row-last_row){
                return false;
            }
        }
        return true;
    }
}
           

2、效率分析

該算法屬于回溯法，時間複雜度為O(n!)，這裡的代碼不調用ArrayList等類庫，直接采用數組進行計算，獲得了較高效率

總結

上一次做這題已經是兩年半之前了，大一大二的時候資料結構算法項目不知道做了幾十個，全都用的C，指針玩得還算熟練，結果現在做這題居然還花了點時間