Huit Reines Heuristiques

Question

Je développe une heuristique pour placer 8 reines sur un échiquier 8x8. chaque carré a son propre numéro d'élimination (pour indiquer combien de cases d'un échiquier vide sont "éliminées" si une reine est placée dans ce carré) et chaque reine doit être placée dans le carré qui a le numéro d'élimination le plus bas. Mon problème est que je ne sais pas quoi faire pour continuer à diminuer les nombres d'élimination spécifiques de leurs carrés appropriés, donc je serai reconnaissant si vous m'aidiez avec cela. un autre problème, je sens que mon code est très compliqué, donc des notes pour le rendre plus simple?

voici mon code

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 

}

ma méthode principale est en classe séparée.

Answer 1

Ce morceau de code est fondamentalement viciée:

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

Vous ne pouvez pas décider où mettre reine 0 sans décider où placer la reine 1 à 8 au même moment. Vous avez mis en place « First Fit »:

Et d'abord Fit ne se traduit pas dans une solution réalisable comme vous pouvez le voir dans l'exemple ci-dessus. More info in this manual (including algorithms that do work).

Voici un algorithme qui fonctionne (mais les échelles horriblement):