Я написал на Java небольшой алгоритм головоломки N-ферзей (с шахматной доской c * c). Ниже вы найдете код моего рекурсивного метода.

Он не находит все решения.

Что делает моя функция

Идея состоит в том, чтобы сделать в основном методе первый вызов моей функции, предоставляя ей максимальное количество ферзей, пока не будет найдено решение, шахматная доска без ферзя и координаты этих новых ферзей: x = 0, y = 0.

Функция будет проходить через шахматную доску. Для каждого квадрата проверяется, может ли быть помещен ферзь (0; 0) (т. е. : нет угрозы). Ферзь (0;0) может быть размещен? Что ж, мы делаем это (модифицируем шахматную доску) и вызываем функцию (рекурсивный вызов). Этот рекурсивный вызов выполняется с помощью: «максимальное количество ферзей — 1», модифицированной шахматной доски и «y 1 нового ферзя» (немного сложнее).

Найдено решение с n = 4 и c = 4 (обычно есть два решения … !)

amp;amp; Qamp;

Qamp;amp;amp;

amp;amp;amp; Q

amp; Qamp;amp;

Недавний код моей функции

 private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) {
    if (nb_queens == 0) { // If there isn't any queen remaining, it means we found a solution
        drawChessboard(chessboard);
        solutions.add(chessboard);
    }

    for(int i = x; i < chessboard.size(); i  ) {
        for (int z = y; z < chessboard.get(i).size(); z  ) {
            if(!canBePlaced(i, z, chessboard)) {
                chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait
                setQueen(nb_queens-1, chessboard, i 1, 0, solutions);
                chessboard.get(z).set(i, false);
            }
        }
    }

}
  

Более старый код

 private static void setQueen(int nb_queens, ArrayList<ArrayList<Boolean>> chessboard, int x, int y, ArrayList<ArrayList<ArrayList<Boolean>>> solutions) {
    if (nb_queens == 0) {
        drawChessboard(chessboard); // Il n'y a plus de reine à placer => on dessine cette solution
        solutions.add(chessboard);
    }

    for(int i = x; i < chessboard.size(); i  ) {
        for (int z = y; z < chessboard.get(i).size(); z  ) {
            if(!isAQueenAlreadyPresent(i, z, chessboard)) {
                chessboard.get(z).set(i, true); // On peut donc placer cette reine(x;y) et on le fait
                setQueen(nb_queens-1, chessboard, i, (z 1 >= WIDTH) ? 0 : z 1, solutions);
                chessboard.get(z).set(i, false);
            }
        }
    }

}
  

Ах да, это потому, что то, как вы вызываете рекурсивно, ваше дело setQueen(nb_queens-1, chessboard, i, z 1, solutions); . z 1 Часть — это проблема, она всегда найдет решение справа от первого ферзя, которого вы разместили на глобальной доске.

Редактировать: ах, вы нашли это раньше, приятно.

Итак, проблема в том, что цикл for действует как an if(z>=y) , потому что он начинается с y . Это нормально, когда i = x (чтение первой строки), но не когда i > x . Итак, простое решение — поместить y = ( i == x ) ? y : 0 сразу после первого for цикла.

Есть еще более чистое решение, например, использование одного индекса для обхода всей шахматной доски.

Я также предлагаю вам переименовать ваш параметр в startX и startY (вместо x и y вы можете использовать x и y в цикле, чтобы быть более понятными).

Редактирование 2: из-за правил игр в одной строке никогда не будет ферзя, поэтому подразделение может выполнить рекурсивный вызов like setQueen(nb_queens-1, chessboard, i 1, 0, solutions); ( i 1 потому что вы начинаете непосредственно со следующей строки). Из-за этого вы даже можете удалить int y параметр из setQueen метода и всегда запускать z loop с 0.