用一維陣列解n皇后問題
使用 2 維的陣列來儲存棋盤 似乎是比較直覺的做法
所以我們會在 map[n][n] 這樣的陣列裡面填上0跟1來表示皇后放在哪裡
接著檢查的方式 就是檢查 每一個行、每一個列、斜角有沒有被放上皇后
OK~ 簡單Easy~
接下來 討論一下利用一維陣列 來儲存
直接將 map[i][j] = 1 取代成 arr[i] = j
檢查的方式呢
檢查map[i][j]第 i 列的部分 由於我們填入的時候 是一列一列的填入 (依照index) 所以可以跳過了
檢查map[i][j]第 j 行的部分 就檢查目前放入陣列的數字有沒有重複就可以了
至於斜角也很簡單 原先map[i][j]與map[[k][l]是否是在斜線的關系
原先使用 |i-k| == |j-l| if (i,j ) != (j, k)來檢查
現在改用 arr[i] = j 與 arr[k] = l 就會變成 |i - k| == |arr[i] - arr[k]| if (i,j ) != (j, k)
import java.util.Arrays;
import java.util.Scanner;
public class JAVA {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = 0 ;
while (cin.hasNext()) {
n = cin.nextInt();
if(n > 0)
printQueen(n);
else break ;
}
}
static void printQueen(int n){
int count = 0 ;
int map[] = new int[n];
int level = 0;
Arrays.fill(map, -1);
for(int i = 0 ; i < n ; i++){
map[i] = level;
count += dfs(n, i, level, map);
map[i] = -1 ;
}
System.out.println(count);
System.out.println();
}
// map[i] = j -->> map[i][j] -> checked
// map[i][j], map[k][l] are conflicted >>> |i-k| == |j-l|
private static int dfs(int n, int i, int level, int[] map) {
if(level == n-1){
printQueenMap(n, map);
return 1 ;
}else{
int count = 0;
for(int k = 0 ; k < n ; k++){
if(map[k] != -1) continue;
boolean flag = true;
for(int ii = 0 ; flag && ii < n ;ii++){
if(map[ii] != -1)
if(Math.abs(ii-k) == Math.abs(map[ii]-level-1)){
flag = false ;
}
}
if(flag){
map[k] = level+1;
count += dfs(n,k,level+1, map);
map[k] = -1;
}
}
return count;
}
}
private static void printQueenMap(int n, int[] map) {
for(int x = 0 ; x < n ; x++){
int tmp = -1;
for(int y = 0; y < n ; y++){
if(map[y] == x){
tmp = y ;
break;
}
}
String XX = repeat("x",n);
System.out.print(XX.substring(n-tmp));
System.out.print("Q");
System.out.println(XX.substring(tmp+1));
}
System.out.println();
}
public static String repeat(String s, int times) {
if (times <= 0) return "";
else return s + repeat(s, times-1);
}
}
