優化N皇后拼圖

我試圖解決在NxN板上定位N皇后沒有行，列和對角線衝突的問題。我使用最小化衝突的算法。首先，在每一列隨機放置一個皇后。之後，在所有衝突女王中隨機選擇一名，併爲她的專欄計算每個可能位置的衝突。然後，女王以最少的衝突移動到最佳位置。它可以工作，但運行速度非常慢。我的目標是讓它快速運行10000個皇后。請問你能否提出一些改進建議，或者在我的邏輯中注意到一些錯誤？優化N皇后拼圖

這裏是我的代碼：

public class Queen { 

int column; 
int row; 
int d1; 
int d2; 

public Queen(int column, int row, int d1, int d2) { 
    super(); 
    this.column = column; 
    this.row = row; 
    this.d1 = d1; 
    this.d2 = d2; 
} 

@Override 
public String toString() { 
    return "Queen [column=" + column + ", row=" + row + ", d1=" + d1 
      + ", d2=" + d2 + "]"; 
} 

@Override 
public boolean equals(Object obj) { 
    return ((Queen)obj).column == this.column && ((Queen)obj).row == this.row; 
} 

}

和：

import java.util.HashSet; 
import java.util.Random; 


public class SolveQueens { 
public static boolean printBoard = false; 
public static int N = 100; 
public static int maxSteps = 2000000; 
public static int[] queens = new int[N]; 
public static Random random = new Random(); 

public static HashSet<Queen> q = new HashSet<Queen>(); 

public static HashSet rowConfl[] = new HashSet[N]; 
public static HashSet d1Confl[] = new HashSet[2*N - 1]; 
public static HashSet d2Confl[] = new HashSet[2*N - 1]; 

public static void init() { 
    int r; 
    rowConfl = new HashSet[N]; 
    d1Confl = new HashSet[2*N - 1]; 
    d2Confl = new HashSet[2*N - 1]; 
    for (int i = 0; i < N; i++) { 
     r = random.nextInt(N); 
     queens[i] = r; 
     Queen k = new Queen(i, r, i + r, N - 1 + i - r); 
     q.add(k); 
     if (rowConfl[k.row] == null) { 
      rowConfl[k.row] = new HashSet<Queen>(); 
     } 
     if (d1Confl[k.d1] == null) { 
      d1Confl[k.d1] = new HashSet<Queen>(); 
     } 
     if (d2Confl[k.d2] == null) { 
      d2Confl[k.d2] = new HashSet<Queen>(); 
     } 
     ((HashSet<Queen>)rowConfl[k.row]).add(k); 
     ((HashSet<Queen>)d1Confl[k.d1]).add(k); 
     ((HashSet<Queen>)d2Confl[k.d2]).add(k); 
    } 
} 

public static void print() { 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      System.out.print(queens[i] == j ? "♕ " : "◻◻◻ "); 
     } 
     System.out.println(); 
    } 
    System.out.println(); 
} 


public static boolean checkItLinear() { 

    Queen r = choseConflictQueen(); 

    if (r == null) { 
     return true; 
    } 

    Queen newQ = findNewBestPosition(r); 

    q.remove(r); 
    q.add(newQ); 
    rowConfl[r.row].remove(r); 
    d1Confl[r.d1].remove(r); 
    d2Confl[r.d2].remove(r); 
    if (rowConfl[newQ.row] == null) { 
     rowConfl[newQ.row] = new HashSet<Queen>(); 
    } 
    if (d1Confl[newQ.d1] == null) { 
     d1Confl[newQ.d1] = new HashSet<Queen>(); 
    } 
    if (d2Confl[newQ.d2] == null) { 
     d2Confl[newQ.d2] = new HashSet<Queen>(); 
    } 
    ((HashSet<Queen>)rowConfl[newQ.row]).add(newQ); 
    ((HashSet<Queen>)d1Confl[newQ.d1]).add(newQ); 
    ((HashSet<Queen>)d2Confl[newQ.d2]).add(newQ); 
    queens[r.column] = newQ.row; 
    return false; 
} 

public static Queen choseConflictQueen() { 

    HashSet<Queen> conflictSet = new HashSet<Queen>(); 
    boolean hasConflicts = false; 

    for (int i = 0; i < 2*N - 1; i++) { 
     if (i < N && rowConfl[i] != null) { 
      hasConflicts = hasConflicts || rowConfl[i].size() > 1; 
      conflictSet.addAll(rowConfl[i]); 
     } 
     if (d1Confl[i] != null) { 
      hasConflicts = hasConflicts || d1Confl[i].size() > 1; 
      conflictSet.addAll(d1Confl[i]); 
     } 
     if (d2Confl[i] != null) { 
      hasConflicts = hasConflicts || d2Confl[i].size() > 1; 
      conflictSet.addAll(d2Confl[i]); 
     } 
    } 
    if (hasConflicts) { 
     int c = random.nextInt(conflictSet.size()); 
     return (Queen) conflictSet.toArray()[c]; 
    } 

    return null; 
} 

public static Queen findNewBestPosition(Queen old) {   
    int[] row = new int[N]; 
    int min = Integer.MAX_VALUE; 
    int minInd = old.row; 

    for (int i = 0; i < N; i++) { 
     if (rowConfl[i] != null) { 
      row[i] = rowConfl[i].size(); 
     } 
     if (d1Confl[old.column + i] != null) { 
      row[i] += d1Confl[old.column + i].size(); 
     } 
     if (d2Confl[N - 1 + old.column - i] != null) { 
      row[i] += d2Confl[N - 1 + old.column - i].size(); 
     } 
     if (i == old.row) { 
      row[i] = row[i] - 3; 
     } 

     if (row[i] <= min && i != minInd) { 
      min = row[i]; 
      minInd = i; 
     } 
    } 

    return new Queen(old.column, minInd, old.column + minInd, N - 1 + old.column - minInd); 
} 

public static void main(String[] args) { 
     long startTime = System.currentTimeMillis(); 
     init(); 
     int steps = 0; 
     while(!checkItLinear()) { 
      if (++steps > maxSteps) { 
       init(); 
       steps = 0; 
      } 
     } 
     long endTime = System.currentTimeMillis(); 
     System.out.println("Done for " + (endTime - startTime) + "ms\n"); 

     if(printBoard){ 
      print(); 
     } 


} 
}

編輯：

下面是刪除一些不使用的對象，並把我一個，小位優化的解決方案皇后在初始化時位於對角位置。

import java.util.Random; 
import java.util.Vector; 


public class SolveQueens { 
public static boolean PRINT_BOARD = true; 
public static int N = 10; 
public static int MAX_STEPS = 5000; 

public static int[] queens = new int[N]; 
public static Random random = new Random(); 


public static int[] rowConfl = new int[N]; 
public static int[] d1Confl = new int[2*N - 1]; 
public static int[] d2Confl = new int[2*N - 1]; 

public static Vector<Integer> conflicts = new Vector<Integer>(); 

public static void init() { 
    random = new Random(); 
    for (int i = 0; i < N; i++) { 
     queens[i] = i; 
    } 
} 

public static int getD1Pos (int col, int row) { 
    return col + row; 
} 

public static int getD2Pos (int col, int row) { 
    return N - 1 + col - row; 
} 

public static void print() { 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      System.out.print(queens[i] == j ? "Q " : "* "); 
     } 
     System.out.println(); 
    } 
    System.out.println(); 
} 


public static boolean hasConflicts() { 

    generateConflicts(); 

    if (conflicts.isEmpty()) { 
     return false; 
    } 

    int r = random.nextInt(conflicts.size()); 
    int conflQueenCol = conflicts.get(r); 
    int currentRow = queens[conflQueenCol]; 
    int bestRow = currentRow; 
    int minConfl = getConflicts(conflQueenCol, queens[conflQueenCol]) - 3; 
    int tempConflCount; 

    for (int i = 0; i < N ; i++) { 
     tempConflCount = getConflicts(conflQueenCol, i); 
     if (i != currentRow && tempConflCount <= minConfl) { 
      minConfl = tempConflCount; 
      bestRow = i; 
     } 
    } 
    queens[conflQueenCol] = bestRow; 
    return true; 
} 

public static void generateConflicts() { 

    conflicts = new Vector<Integer>(); 

    rowConfl = new int[N]; 
    d1Confl = new int[2*N - 1]; 
    d2Confl = new int[2*N - 1]; 

    for (int i = 0; i < N; i++) { 
     int r = queens[i]; 
     rowConfl[r]++; 
     d1Confl[getD1Pos(i, r)]++; 
     d2Confl[getD2Pos(i, r)]++; 
    } 

    for (int i = 0; i < N; i++) { 
     int conflictsCount = getConflicts(i, queens[i]) - 3; 
     if (conflictsCount > 0) { 
      conflicts.add(i); 
     } 
    } 
} 

public static int getConflicts(int col, int row) { 
    return rowConfl[row] + d1Confl[getD1Pos(col, row)] + d2Confl[getD2Pos(col, row)]; 
} 



public static void main(String[] args) { 
     long startTime = System.currentTimeMillis(); 
     init(); 
     int steps = 0; 
     while(hasConflicts()) { 
      if (++steps > MAX_STEPS) { 
       init(); 
       steps = 0; 
      } 
     } 
     long endTime = System.currentTimeMillis(); 
     System.out.println("Done for " + (endTime - startTime) + "ms\n"); 

     if(PRINT_BOARD){ 
      print(); 
     } 
}

}

來源

2011-11-05 brain_damage

你知道10k皇后的獨特解決方案的數量究竟有多龐大嗎？ – Voo

是的。但我只尋找一種解決方案，而不是全部。 –

這太晚了，但這可以幫助http://cse.unl.edu/~choueiry/Documents/Sosic-Gu-N-queens-1990.pdf –

評論將是有益的:)

而不是重新創建衝突，而且你的「最糟糕的衝突」女王的一切，你可以創建它一次，然後只更新改變行/列？

編輯0：我試着玩了一下你的代碼。由於代碼是隨機的，所以很難發現變化是否好，因爲你可能從一個良好的初始狀態或糟糕的狀態開始。我試着用10個皇后進行10次運行，得到了截然不同的答案，但結果如下。

我僞造了一下，看看哪些語句執行得最多，結果是chooseConflictQueen中的內部循環語句執行得最多。我試圖插入一個休息時間來拉第一個衝突女王如果發現，但它似乎沒有多大幫助。

Stats

是花了超過一秒鐘分組僅運行：

More Stats

我知道我只有10次，這是不是真的足以成爲有效的統計，但嘿。

因此添加中斷似乎沒有幫助。我認爲一個建設性的解決方案可能會更快，但隨機性會再次難以檢查。

來源

2011-11-05 19:32:26 Kane

謝謝！我編輯它:)但它仍然非常緩慢。 –

您的方法很好：具有最小衝突約束的局部搜索算法。我會建議嘗試改善你的初始狀態。而不是隨機放置所有皇后，每列1個，嘗試放置它們，以便最大限度地減少衝突次數。一個例子就是根據前一個人的位置嘗試給你下一個皇后，或者前兩個皇后的位置......然後你本地搜索的問題就不那麼成問題了。

來源

2011-11-06 07:42:11 dmn

我會盡力的。 Благодаря！ :) –

如果您隨機選擇，則可以選擇相同的狀態作爲以前的狀態。從理論上講，即使有解決方案，也可能找不到解決方案。

我想你會更好地正常迭代通過狀態。

另外，你確定8x8以外的板子是否可以解決？通過檢查，2x2不是，3x3不是，4x4不是。

來源

2011-11-06 19:34:45 Bohemian

測試n皇后的每個可能的狀態意味着我們有可能的排序（即n = 8，即4.426.165.368）。這對於工作來說太大了。也是的，解決方案的數量爆炸得非常快，所以對於更大的領域確實存在解決方案。 – Voo

@Voo是的，但有些位置是他人的反射/旋轉，因此是「相同的」，所以你可以識別這些並消除許多分支，可能以你迭代的方式（而不是存儲n^2個狀態！）。這就像[組合]（http://en.wikipedia.org/wiki/Combination）和[排列組合]（http://en.wikipedia.org/wiki/Permutation）之間的區別。 – Bohemian

在這種情況下，您必須存儲計算後的狀態，這些狀態也會發生爆炸 - 因此需要一些記憶，但是如何計算相同的情況會產生問題（您需要某種方法來規範matrizes，以便查找它們）。或者，也許我們可以巧妙地分支，不知道。但即使你只需要計算每個10^9的狀態，我們也會看到10^232個可能的狀態。這是不可能的 - 你需要用一些聰明的啓發式來確定性地解決這個問題。 – Voo

優化N皇后拼圖

回答

相關問題