生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法-- 八皇后问题（多种实现方案）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
八皇后問題解法一(排列篩選法)
- 本篇我們承接上一篇中的思想，想到了一個經典的算法題，八皇后問題：
- 題目：在8*8的國際象棋上擺放8個皇后，使得其互相不能攻擊，即任意兩個換后不能在同一行，同一列，或者同一對角線上。如下圖中所示，就是一個符合預期的擺放方式，問總共有多少中擺放方式。
public class EightQueen {private static final List<Integer[]> myQueen
= new ArrayList<>();public static void main(String[] args
) {Integer[] eight
= {0,1,2,3,4,5,6,7};getEightQueenPerMutain(eight
, 0);List<Integer[]> realQueen
= checkQueen(myQueen
);for (Integer[] integers
: realQueen
) {for (int i
= 0; i
< integers
.length
; i
++) {System.out
.print(integers
[i
]+",");}System.out
.println();}}public static List<Integer[]> checkQueen(List<Integer[]> myQueen
){List<Integer[]> realEightQueen
= new ArrayList<>();for (Integer[] integers
: myQueen
) {boolean isCheck
= true;for (int i
= 0; i
< integers
.length
; i
++) {if(!isCheck
){break;}for (int j
= i
+1; j
<integers
.length
;j
++){if((i
-j
) == (integers
[i
] - integers
[j
])|| (j
-i
) == (integers
[i
] - integers
[j
])){isCheck
= false;break;}}}if(isCheck
){realEightQueen
.add(integers
);}}return realEightQueen
;}public static void getEightQueenPerMutain(Integer[] eight
, Integer start
){if(eight
== null || eight
.length
<= 1 || start
== eight
.length
-1){Integer[] newEight
= new Integer[eight
.length
];for (int i
= 0; i
< eight
.length
; i
++) {newEight
[i
] = eight
[i
];}myQueen
.add(newEight
);}for (int i
= start
; i
<= eight
.length
-1; i
++) {Integer temp
= eight
[start
];eight
[start
] = eight
[i
];eight
[i
] = temp
;getEightQueenPerMutain(eight
, start
+1);temp
= eight
[start
];eight
[start
] = eight
[i
];eight
[i
] = temp
;}}
}
八皇后問題解法二（動態規劃）
-
接上文中，依然可以用數組 myQueen[8] = {4,2,0,5,7,1,3,6} 來標識這種擺放的可能
-
那么上文中將所有排列列舉出來后在對排列集合進行篩選得到最終的八皇后集合
-
類似的思路，我們用窮舉法將數組myQueen中包含0 ~ 7 的所有數字的可能一一列舉，并且實時篩選，這樣我們可以一個步驟直接得到想要的集合
-
經過如上分析有如下代碼：
public class EightQueen {private static final List<Integer[]> myQueen
= new ArrayList<>();public static void main(String[] args
) {for (int i
= 0; i
< 8; i
++) {Integer[] eight
= new Integer[8];getEightQueen(eight
, i
);}for (Integer[] integers
: myQueen
) {for (int i
= 0; i
< integers
.length
; i
++) {System.out
.print(integers
[i
] + ",");}System.out
.println();}System.out
.println(myQueen
.size());}public static void getEightQueen(Integer[] queen
, int start
){for (int i
= 0; i
< 8; i
++) {queen
[start
] = i
;if(checkout(queen
, start
)){if(start
== queen
.length
-1){Integer[] realQueen
= new Integer[8];for (int i1
= 0; i1
< queen
.length
; i1
++) {realQueen
[i1
] = queen
[i1
];}myQueen
.add(realQueen
);}else {getEightQueen(queen
, start
+ 1);}}}}public static boolean checkout(Integer[] queen
, Integer end
){Set<Integer> checkRepeat
= new HashSet<>();for (int i
= 0; i
<= end
; i
++) {if(checkRepeat
.contains(queen
[i
])){return false;}checkRepeat
.add(queen
[i
]);for(int j
= i
+1; j
<= end
; j
++){if(queen
[i
] == null || queen
[j
] == null){return false;}if((i
-j
) == (queen
[i
]- queen
[j
]) || (j
-i
) == (queen
[i
] - queen
[j
])){return false;}}}return true;}
}
八皇后問題解法三（回朔遞歸）
- 依然可以用數組 myQueen[8] = {4,2,0,5,7,1,3,6} 來標識這種擺放的可能
- 首先將第一個皇后放入第一列位置
- 接著將第二個皇后分別放入第二三四等之后的位置，每次分別去檢查放入的位置是否與之前的位置中放入的皇后是否在同一列，同一對角線
- 接著依次對地三個，第四個，直到第八個皇后重復第二步驟，找出每個皇后所有合法的位置
- 方法三 與方法二的實現方式非常類似，區別在于篩選，方法三種的篩選只需要對比最后一個元素與之前的元素是否沖突，在方法三中是每個皇后的位置依次檢查，當進行到第5個皇后的時候，能保證前4個皇后的位置都是合法的，無需在檢查之前的。
- 具體實現方案如下，方法三實現方案更好理解。
public class EightQueen {private static final List<Integer[]> myQueen
= new ArrayList<>();public static void main(String[] args
) {getEightQueenRetro();print();}public static void print() {for (Integer[] integers
: myQueen
) {for (int i
= 0; i
< integers
.length
; i
++) {System.out
.print(integers
[i
] + ",");}System.out
.println();}System.out
.println(myQueen
.size());}public static void getEightQueenRetro() {Integer[] eight
= new Integer[8];check(eight
, 0);}public static void check(Integer[] eight
, int n
) {if (n
== eight
.length
) {myQueen
.add(Arrays.copyOf(eight
, eight
.length
));return;}for (int i
= 0; i
< eight
.length
; i
++) {eight
[n
] = i
;if(judge(eight
, n
)){check(eight
, n
+1);}}}public static boolean judge(Integer[] eight
, int n
){for(int i
=0;i
<n
;i
++){if(eight
[i
] == eight
[n
] || Math.abs(n
-i
) == Math.abs(eight
[n
] - eight
[i
])){return false;}}return true;}
}
總結
- 以上兩個方法的整體思路類似，當題目需要我們按照一定規則擺放若干個數字的時候，我們可以先求出這些數字的所有可能，然后在一一判斷每個組合是否滿足題目給定的要求。
- 方法一利用上一篇中的排列的算法得出所有排列可能，接著篩選，時間復雜度O( n3 )
- 方法二 利用遞歸窮舉方法得出所有數字的可能，并同時篩選，時間復雜度也是O(n3)
- 兩種算法的時間復雜度都并非很優，如有更好的算法思想，求在評論指出
上一篇：數據結構與算法–字符串的排列組合問題
下一篇：數據結構與算法-- 數組中出現次數超過一半的數字（時間復雜度的討論）
總結
以上是生活随笔為你收集整理的数据结构与算法-- 八皇后问题（多种实现方案）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
