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 !