Решение головоломки N-Queens - не могу понять

Прежде всего, неважно, используете ли вы столбцы или строки - результат будет одинаковым, потому что проблема симметрична. Эта симметрия создаст некоторую путаницу; будьте готовы к этому.

Не обращая внимания на ваши конкретные вопросы, идея здесь состоит в том, чтобы выполнить рекурсию. Задача говорит о расстановке 8 ферзей. Если вы поставили k-1 ферзей, вы получили «позицию». Из каждой позиции вы можете получить несколько «расширенных» позиций, в которые вы поместили еще одного ферзя (так что есть k ферзей). Таким образом, для каждого набора позиций с k-1 ферзями есть набор позиций с k ферзями.

Этот набор нужно «отфильтровать» - удалить из него все недопустимые позиции. В некоторых случаях он будет пустым (разместить другого ферзя невозможно); это ни в коем случае не особая ситуация - этого будет много. В остальных случаях (на самом деле, в большинстве случаев) он будет большим. Например, для «пустой» позиции - без ферзей - будет несколько (фактически 8 - см. Ниже) «расширенных позиций» с 1 размещенным ферзем.

Теперь не имеет значения, как вы разместите дополнительную королеву. В общем случае (при размещении любой шахматной фигуры) вы должны разместить ее на любом свободном квадрате (и убедиться, что вы действительно отметили все из них). Поскольку ферзи атакуют так, как они это делают, в каждом столбце должен быть ровно один ферзь, поэтому достаточно проверить только 8 возможных позиций для каждого ферзя. Например, в «следующем ряду». Или в «следующий столбец» - тоже сработает.

Посмотрим, смогу ли я разобраться с этим для вас. Я собираюсь разрезать доску до 5x5, чтобы закрыть комбинаторный взрыв.

Вы начинаете с пустой доски, 0 ферзей. Теперь вы хотите поместить ферзя в каждую допустимую позицию столбца 1. Создайте следующий блокнот:

1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0

Теперь вы идете вниз по колонне и устраняете каждую незаконно размещенную королеву ... ну, это было легко! Все пять законны. Теперь вы создаете позицию для каждого законного места размещения. Вы получаете пять позиций из этого:

1 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    1 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    1 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    1 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    1 0 0 0 0

Я отложу пока последние четыре и продолжу только с первым.

Это позиция с одним ферзем, поэтому мы хотим поместить ферзя во второй столбец. Снова делаем блокнот, помещая ферзя в каждый ряд:

1 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0

Устранение незаконных размещений:

1 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0

Создайте новую позицию для каждого легального размещения:

1 0 0 0 0    1 0 0 0 0    1 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 1 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 1 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 1 0 0 0

На этом этапе, если вы проводите обход пространства решений в ширину, вы помещаете эти позиции в какой-то список для дальнейшей обработки, а затем выполняете вторую позицию с 1 ферзью. Если вы делаете в первую очередь глубину (что я рекомендую для экономии памяти), поместите 2-ю и 3-ю позиции выше в список с оставшимися четырьмя решениями с 1 ферзью и сразу же работайте с первой позицией чуть выше.

Поместите ферзя в каждый ряд столбца 3:

1 0 1 0 0
0 0 1 0 0
0 1 1 0 0
0 0 1 0 0
0 0 1 0 0

Устранение незаконных:

1 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 1 0 0

И сгенерируйте новую позицию для каждого легального размещения - а есть только одна.

Продолжая еще два шага, мы получаем наше первое решение:

1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0

Это называется «удачей» ... мы часто не получаем решения на первой ветке. Например, следуя этой позиции по первой ветви ...

1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0

Следующий шаг дает вам

1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 0 0 0

Теперь нет законного места для столбца 4. В этом случае вы должны сдаться и занять следующую легальную позицию в вашем списке ожидания.

Я настоятельно рекомендую рекурсивное решение, ориентированное на глубину. Это позволяет вам хранить список позиций локально. В самом глубоком месте у вас может быть только 8 активных вызовов функции добавления ферзя, каждый из которых тривиально ограничен 8- k позициями (без учета диагональных атак); реальность несколько меньше, так что у вас никогда не будет более 25 активных позиций на всех уровнях вместе взятых. Прежде чем вы закончите размещать вторую королеву на всех ветвях, она превысит это значение.

Формулировка решения, а точнее описание алгоритма, возможно, несколько запутана.

В основном это предлагает

• сначала создайте все возможные комбинации из восьми ферзей на шахматной доске, по одному ферзю на столбец. Предписанные шаги для этого:

  • place a queen in column 1, on the first row. Then place the next queen in column 2, on the first row. And so on, to column 8. (Obviously, this solution is invalid.) This is the first position (for all 8 queens).
  • затем сделайте то же самое, но для ферзя в столбце 8 (Q8) поместите его в строку номер 2. Это позиция номер 2.
  • затем Q8 в строке 3. И т.д., пока Q8 не пройдет все строки. Это восемь позиций.
  • затем Q1 – Q6 сохраняют строку 1, Q7 перемещается в строку 2, Q8 начинается снова в строке 1.
  • снова, как и раньше, переместите Q8 между строками 1 и 8. Еще 8 позиций.
  • От Q1 до Q6 по-прежнему строки 1, Q7 до строки 3, Q8 строки с 1 по 8.
  • И так до тех пор, пока Q7 и Q8 не дойдут до строки 8.
  • Теперь очередь Q6 перейти к строке 2. В остальном, повторите шаблоны для Q8 и Q7 еще раз. Вы можете увидеть рекурсию.

  Приведенное выше генерирует 8 ^ 8 = 16777216 решений, многие из которых недопустимы. Это «расширенный набор позиций».

• теперь, из всех этих решений («позиций»), пройдитесь по ним одно за другим и оставьте те, в которых ни одна из ферзей не сможет занять другую (вам нужно будет пройти по 7 ферзей для каждой позиции, проверяя их строки, столбцы и диагонали; тогда Q8 учитывается автоматически).

  Если вы сохраните только допустимые позиции, у вас будут все допустимые конфигурации для головоломки с восемью ферзями.

Код Java, использующий отслеживание с возвратом, измените переменную SIZE, чтобы сделать ее универсальной

public class EightQueens {

    private final int SIZE = 10;

    private final int safe = 0;
    private final int cut = 1;
    private final int queen = 2;

    private int[][] mat = new int[SIZE][SIZE];

    private EightQueens() {
        for (int x = 0; x < SIZE; x++) {
            for (int y = 0; y < SIZE; y++) {
                mat[x][y] = safe;
            }
        }
    }

    private void solveAll(){
        solve(mat);
    }


    private int[][] copy(int[][] mat){
        int[][] test = new int[SIZE][SIZE];
        for (int x = 0; x < SIZE; x++) {
            for (int y = 0; y < SIZE; y++) {
                test[x][y] = mat[x][y];
            }
        }
        return test;
    }

    private void solve(int[][] matrix) {

       // System.out.println("solving ");
       // printMat(matrix);

        if (solved(matrix)) {
            printMat(matrix);
            return;
        }
        int unsafe;
        for (int x = 0; x < SIZE; x++) {
            unsafe = 0;
            for (int y = 0; y < SIZE; y++) {
                if(matrix[x][y] == safe){

                    int[][] test = copy(matrix);
                    test[x][y] = queen;
                    //mark row
                    for(int z =0 ;z<SIZE;z++){
                        if(z == x){
                            continue;
                        }
                        test[z][y] = cut;
                    }
                    //mark col
                    for(int z =0 ;z<SIZE;z++){
                        if(z == y){
                            continue;
                        }
                        test[x][z] = cut;
                    }

                    //first diagonal
                    int a = x+1;
                    int b = y+1;
                    while(a<SIZE && b <  SIZE){
                        test[a][b] = cut;
                        a++;b++;
                    }
                    a = x-1;
                    b = y-1;
                    while(a>=0 && b >=0){
                        test[a][b] = cut;
                        a--;b--;
                    }

                    //second diagonal
                    a = x+1;
                    b = y-1;
                    while(a<SIZE && b >=  0){
                        test[a][b] = cut;
                        a++;b--;
                    }
                    a = x-1;
                    b = y+1;
                    while(a>=0 && b < SIZE){
                        test[a][b] = cut;
                        a--;b++;
                    }

                    solve(test);
                }else {
                    unsafe++;
                    if(unsafe == SIZE){
                        return;
                    }
                }
            }
        }
    }

    private void printMat(int[][] mat){
        for (int x = 0; x < SIZE; x++) {
            for (int y = 0; y < SIZE; y++) {
                System.out.print(mat[x][y]+" ");
            }
            System.out.println();
        }
        System.out.println("_______________________________________________");
    }

    private boolean solved(int[][] mat) {
        int count = 0;
        for (int x = 0; x < SIZE; x++) {
            for (int y = 0; y < SIZE; y++) {
                if (mat[x][y] == queen) {
                    count++;
                }
            }
        }
        if (count == SIZE) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args){
        EightQueens eightQueens = new EightQueens();
        eightQueens.solveAll();
    }

}