On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Yann en début de semaine !
On place une reine par ligne, à la première place possible. Puis on passe à la ligne suivante. Si une ligne ne peut être remplie (aucune solution possible), on met à jour la ligne précédente en incrémentant la position.
public class QueensSolver {
public static int LENGTH = 8;
public static boolean[][] board = new boolean[LENGTH][LENGTH];
public static void main(String[] args) {
int row = 0;
while (row >= 0 && row < LENGTH) {
// Try to place queen on current row
if (placeFoundForQueenOnRow(row)) {
row++; // If placed, goes to next row
} else {
row--; // If no place available, previous row must be reworked
}
}
displayBoard();
}
/**
* Place the queen on the first next available spot on the row
* @param row
* @return If a new place is found
*/
public static boolean placeFoundForQueenOnRow(int row) {
int newCol = 0;
// Search for current queen
for (int j = 0; j < LENGTH; j++) {
if (board[row][j]) {
board[row][j] = false; // remove current queen
newCol = j + 1; // Place cursor after current
}
}
while (newCol < LENGTH) {
if (!isThreatened(row, newCol)) {
board[row][newCol] = true; // place new queen
return true;
}
newCol++;
}
return false; // No position available
}
// Check is position(i,j) is threatened
public static boolean isThreatened(int i, int j) {
// Check row & diagonals (upward only)
for (int k = 1; k <= i; k++) {
if (containsQueen(i - k, j) || containsQueen(i - k, j - k) || containsQueen(i - k, j + k)) return true;
}
return false;
}
// Check parameters in range & queen presence
public static boolean containsQueen(int i, int j) {
return i >= 0 && i < LENGTH && j >= 0 && j < LENGTH && board[i][j];
}
// Display board
public static void displayBoard() {
StringBuilder sb = new StringBuilder();
sb.append("\ta\tb\tc\td\te\tf\tg\th\n")
.append("---------------------------------");
for (int i = 0; i < LENGTH; i++) {
sb.append("\n").append(i).append("|\t");
for (int j = 0; j < LENGTH; j++) {
sb.append(board[i][j]?'X':'o')
.append("\t");
}
}
System.out.println(sb.toString());
}
}
A bientôt pour un nouveau #KataOfTheWeek !