Évitons un conflit fratricide

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