java - 8皇后回溯(n变化)

Question

问题是当我的程序回溯时它会以某种方式将 n 更改为 n-1你能告诉我发生在我的代码的哪一行吗？示例:

1. 22 步骤 0 2 4 1 3 6 0 0 n in bool -> 5 n in bool -> 5 i = 7 n -> 5
2. 23 步骤 0 2 4 1 3 7 0 0 n in bool -> 5 n in bool -> 5 n in bool -> 5 i = 4 n -> 4
3. 24 步骤 0 2 4 1 4 7 0 0 n in bool -> 4 i = 5 n -> 4

<小时/>

正如我们所见，我在步骤 22 中得到 n = 5，在步骤 23 中得到 n = 4；问题:我的代码中的 n 如何变为 n-1？

来源(代码没有任何错误):

import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Arrays;

public class Queens {

    public static FileOutputStream Output;
    public static PrintStream file;
    public static int z = 1;
    public static String[] LentosRaides = {"a", "b", "c", "d", "e", "f", "g", "h"};
    public static String[] LentosSkaiciai = {"8", "7", "6", "5", "4", "3", "2", "1"};

    /***********************************************************************
     * Grazinam true jei kitu valdoviu padietis q[n] nesikonfliktuoja su kitomis
     * valdovemis q[0] iki q[n-1]
     ***********************************************************************/
    public static boolean arNuoseklus(int[] q, int n) {
        for (int i = 0; i < n; i++) {
            System.out.println("n in bool -> " + n);
//            System.out.println("i = " +i+ "n = " +n);
//            System.out.println("q[i] = "+q[i]+" q[n] = "+q[n]);
//            System.out.print("q[i] - q[n] = ");
//            System.out.println(q[i] - q[n]);
//            System.out.print(" q[n] - q[i] = ");
//            System.out.println(q[n] - q[i]);
//            System.out.println();


            if (q[i] == q[n]) {
                return false;   // tapati skiltis(kolona)
            }
            if ((q[i] - q[n]) == (n - i)) {
                return false;   // ta pati pagrindine diagonale major

            }
            if ((q[n] - q[i]) == (n - i)) {
                return false;   // ta pati mazesnine diagonale minor
            }

        }
        return true;
    }

    /***********************************************************************
     * Spausdinimas i tekstini faila: Rezultatai.txt ir i output'a
     ***********************************************************************/
    public static void printQueens(int[] q) {
        int N = q.length;
        String Temp[] = new String[N];
        System.out.println(z);
        for (int y = 0; y < N; y++) {
            Temp[y] = (LentosRaides[q[y]] + LentosSkaiciai[y]);
        }

        Arrays.sort(Temp);
        System.out.println(Arrays.asList(Temp));
        file.print(z);
        file.println(Arrays.asList(Temp));
        z++;

        for (int j = 0; j < N; j++) {
            System.out.print(q[j] + " ");
        }

//        System.out.println(" ");
//        System.out.print(" ");
//
//        for (int u = 0; u < N; u++) {
//            System.out.print(" " + LentosRaides[u]);
//        }
//
//        System.out.println();
//
//        for (int i = 0; i < N; i++) {
//            System.out.print(LentosSkaiciai[i] + " ");
//            for (int j = 0; j < N; j++) {
//
//                if (q[i] == j) {
//                    System.out.print("V ");
//                } else {
//                    System.out.print("* ");
//                }
//            }
//
//            System.out.println();
//        }


        System.out.println();
    }

    /***********************************************************************
     *  Visu kombinaciju bandimas naudojant "backtracking'a"
     *  numeravimas -> bandimas pastatyti Valdove nuo 0 iki 7 pozicijos
     *  naudojant patikrinima arNuoseklus
     ***********************************************************************/
    public static void numeravimas2(int N) {
        int[] a = new int[N];
        numeravimas(a, 0);

    }

    public static void numeravimas(int[] q, int n) {
        System.out.println("n -> " + n);
        int N = q.length;

        if (n == N) {
            printQueens(q);
          //  System.out.println("o/ ");

        } else {
            for (int i = 0; i < N; i++) {
                q[n] = i;
                System.out.println(" i =  " + i);
                System.out.println("n -> " + n);
                printQueens(q);
                if (arNuoseklus(q, n)) {
                    numeravimas(q, n + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int N = 8;

        try {
            Output = new FileOutputStream("Rezultatai.txt");
            file = new PrintStream(Output);
        } catch (Exception e) {
            System.out.println("Neimanoma pasiekti failo");
        }

        numeravimas2(N);

    }
}

Answer 1

并没有真正减少。它位于:

public static void numeravimas(int[] q, int n) {
   ...
        for (int i = 0; i < N; i++) {
            ...
            System.out.println("n -> " + n);
             ...
                numeravimas(q, n + 1);
        }
}

所以当 n = 5 ，它将打印 n -> 5 N次。然而在N之间 5, numeravimas(q, 6) 的打印输出被调用，它本身调用 numeravimas(q, 7) ...所以你会得到 n 的各种值的一些交织。来自 for 循环的组合 i以及 numeravimas 的递归调用.