Cette semaine, c'est Yann qui vous propose un #KataOfTheWeek : Un royaume pacifiste
Briefing du Kata :
Caractéristiques du royaume ? Le roi des Tchèques vous explique que son royaume est un plateau qui ressemble (étrangement) à un damier 8x8.
Chaque reine devra donc être placée sur le plateau, sans menacer ses soeurs (ou être en menace… cela dépend du point de vue).
Chess 101
"La dame est une pièce à longue portée, capable de se mouvoir en ligne droite, verticalement, horizontalement, et diagonalement, sur un nombre quelconque de cases inoccupées comme le montre le diagramme sur la gauche" Wikipedia
Une dame (ou reine selon le jargon de la province) est donc menacée si elle se trouve sur la même ligne, colonne, ou diagonale qu'une autre reine.
A vous de jouer !
Note: plusieurs solutions sont possibles (12 sans les symétries), il s'agit d'en trouver une pour préserver le royaume
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur en Java :
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());
}
}
Votre équipe TakiVeille
