八皇后啓發式

Question

我正在開發一種啓發式方法來在8x8棋盤上放置8個皇后。每個正方形都有自己的消除數（用於表示如果一個皇后放在那個正方形中，空棋盤有多少個正方形被「消除」），並且每個正方形應放置在消除數最少的正方形中。

我的問題是，我不知道該怎麼做才能減少它們相應的正方形的具體消除數量，所以我會很感激你是否幫助過我。 另一個問題，我覺得我的代碼非常複雜，所以任何筆記都可以使它更簡單？

這裏是我的代碼

public class Queen { 
private final int SIZE = 8; 
private int board[][] = new int[SIZE][SIZE]; // 8x8 board 
private int hor[] = new int[SIZE]; // horizontal moves 
private int ver[] = new int[SIZE]; // vertical moves 
private int lowestValue = 22; 
private int[][] queens = new int[SIZE][2]; // 8 queens 

public Queen() { 
    // initialize each square with its own elimination number 
    for (int row = 0; row < board.length; row++) { 
     for (int col = 0; col < board[row].length; col++) { 
      if (row == 0 || row == 7 || ((row >= 1 && row <= 6) && (col == 0 || col == 7))) { 
       board[row][col] = 22; 
      } 
      else if ((row == 1 || row == 6) && (col >= 1 && col <= 6) || (row > 1 && row < 6) && (col == 1 || col == 6)) { 
       board[row][col] = 24; 
      } 
      else if ((row == 2 || row == 5) && (col >= 2 && col <= 5)|| (row > 2 && row < 5) && (col == 2 || col == 5)){ 
       board[row][col] = 26; 
      } 
      else if ((row == 3 || row == 4) && (col >= 3 && col <= 4)){ 
       board[row][col] = 28; 
      } 

     } 
    }// end initializing 

    // initialize moves 
    //right 
    hor[0] = 1; 
    ver[0] = 0; 
    //left 
    hor[1] = -1; 
    ver[1] = 0; 
    //up 
    hor[2] = 0; 
    ver[2] = -1; 
    //down 
    hor[3] = 0; 
    ver[3] = 1; 
    //up right 
    hor[4] = 1; 
    ver[4] = -1; 
    hor[7] = -1; 
    ver[7] = 1; 
    //up left 
    hor[5] = -1; 
    ver[5] = -1; 
    //down right 
    hor[6] = 1; 
    ver[6] = 1; 
    // down left 

    for (int queen = 0; queen < queens.length; queen++) { 
     placeQueens(queen); 
    } 
    displayBoard(); 
}// end constructor 

// eliminate squares according to the place of the queen 
private void eliminate (int queen_row, int queen_col) { 

    // eliminate diagonal 
    int rowCopy = queen_row;// helper row 
    int colCopy = queen_col;// helper column 
    try { 
     // eliminate up right 
     for (int move = 0; move < 8; move++) { 
      rowCopy += ver[4]; 
      colCopy += hor[4]; 
      if (board[rowCopy][colCopy] > 0) { 
       board[rowCopy][colCopy] = 0; 
      } 
     } 
    } 
    catch (ArrayIndexOutOfBoundsException e) {  
    } 

    try { 
     rowCopy = queen_row; 
     colCopy = queen_col; 
     // eliminate up left 
     for (int move = 0; move < 8; move++) { 
      rowCopy += ver[5]; 
      colCopy += hor[5]; 
      if (board[rowCopy][colCopy] > 0) { 
      board[rowCopy][colCopy] = 0; 
      } 
     } 
    } 
    catch (ArrayIndexOutOfBoundsException e) { 
    } 

    try { 
     rowCopy = queen_row; 
     colCopy = queen_col; 
     // eliminate down right 
     for (int move = 0; move < 8; move++) { 
      rowCopy += ver[6]; 
      colCopy += hor[6]; 
      if (board[rowCopy][colCopy] > 0) { 
      board[rowCopy][colCopy] = 0; 
      } 
     } 
    } 
    catch (ArrayIndexOutOfBoundsException e) { 
    } 
    try { 
     rowCopy = queen_row; 
     colCopy = queen_col; 
     // eliminate down left 
     for (int move = 0; move < 8; move++) { 
      rowCopy += ver[7]; 
      colCopy += hor[7]; 
      if (board[rowCopy][colCopy] > 0) { 
      board[rowCopy][colCopy] = 0; 
      } 
     } 
    } 
    catch (ArrayIndexOutOfBoundsException e) { 
    } 

    // eliminate row 
    for (int col = 0; col < 8;col++) { 
     if (board[queen_row][col] > 0) { 
     board[queen_row][col] = 0; 
     } 
    } 
    // eliminate col 
    for (int row = 0; row < 8; row++) { 
     if (board[row][queen_col] > 0) { 
     board[row][queen_col] = 0; 
     } 
    } 

}// end elimination 

// decrease elimination number of each square 
public void decreaseElimination() { 


}// end decrease elimination 

public void countEliminated() { 
    int counter = 0; 
    for (int row = 0; row < board.length; row++) { 
     for (int col = 0; col < board[row].length; col++) { 
      if (board[row][col] == 0) { 
       counter++; 
      } 

     } 
    } 
    System.out.printf("%d squares eliminated\n", counter); 

} 

public void placeQueens(int queenNum) { 
    int targetRow; 
    int targetCol; 
    // find lowest elimination number 
    for (int row = 0; row < board.length; row++) { 
     for (int col = 0; col < board[row].length; col++) { 
      if (board[row][col] > 0 && board[row][col] < lowestValue) { 
       lowestValue = board[row][col]; 
       targetRow = row; 
       targetCol = col; 

       queens[queenNum][0] = targetRow; 
       queens[queenNum][1] = targetCol; 
      } 
     } 
    } 

    System.out.printf("queen %d has been placed in [%d][%d]\n", queenNum + 1, queens[queenNum][0], queens[queenNum][1]); 
    eliminate(queens[queenNum][0], queens[queenNum][1]); 
    decreaseElimination(); 
    countEliminated(); 

} 

// display board 
public void displayBoard() { 

    for (int row = 0; row < board.length; row++) { 
     for (int col = 0; col < board[row].length; col++) { 
       System.out.printf("|%2d|", board[row][col]); // display elimination number of each square 
     } 
     System.out.println(); 
    } 

}// end displayBoard 

}

我的主要方法是在單獨的類。

Answer 1

這段代碼是天生的缺陷：

for (int queen = 0; queen < queens.length; queen++) { 
    placeQueens(queen); 
} 

你不能決定在哪裏放置大號0沒有決定在哪裏把女王1至8在精確的同一時間。你已經實現了「第一嵌入」：

而且第一嵌入不會導致一個可行的解決方案，你可以在上面的例子中看到的。 More info in this manual (including algorithms that do work).

這裏有一個算法，不工作（但可怕的尺度）：