用一維陣列解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)

   OK~ 所以完成使用一維陣列取代 二維陣列 解 n皇后問題~

a160: 柏森想要下棋!!!
http://zerojudge.tw/ShowProblem?problemid=a160

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);
    }
}