Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
293 views
in Technique[技术] by (71.8m points)

backtracking - Explanation of 8-Queen solution Java code.

I found a 8-Queen solution that I was able to compile and run in Eclipse. I believe this solution follows the backtracking approach and meat of the work is done in the solution and unsafe functions, but I am having a hard time understanding the code paths in there. Can someone please help me understand what this code is doing.

My Source - http://rosettacode.org/wiki/N-queens_problem#Java I verified the output against the 92 solutions published on other sources. Looks good. So I know the code works.

I have tried to format it and add some basic notes to clear things up -

private static int[] b = new int[8];
private static int s = 0;

public static void main(String[] args) {
    // solution from - http://rosettacode.org/wiki/N-queens_problem#Java
    new QueenN();
}

public QueenN() {
    solution();
}

public void solution() {
    int y = 0;
    b[0] = -1;
    while (y >= 0) {
        do {
            b[y]++;
        } while ((b[y] < 8) && unsafe(y));

        if (b[y] < 8) {

            if (y < 7) {
                b[++y] = -1;
            } else {
                putboard();
            }

        } else {
            y--;
        }
    }
}

// check if queen placement clashes with other queens
public static boolean unsafe(int y) {
    int x = b[y];
    for (int i = 1; i <= y; i++) {
        int t = b[y - i];
        if (t == x || t == x - i || t == x + i) {
            return true;
        }
    }
    return false;
}

// printing solution
public static void putboard() {
    System.out.println("

Solution " + (++s));
    for (int y = 0; y < 8; y++) {
        for (int x = 0; x < 8; x++) {
            if (b[y] == x)
                System.out.print("|Q");
            else
                System.out.print("|_");
        }
        System.out.println("|");
    }
}

End.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Let's try to understand the code step by step. First of all, we call the function solution(), which is what leads to the execution of the puzzle answer.

Solution funcion:

public void solution() {
    int y = 0;
    b[0] = -1;
    while (y >= 0) {
        do {
            b[y]++; //if last cell was unsafe or we reached the end of the board, we go for the next row.
        } while ((b[y] < 8) && unsafe(y)); //Checks whether it's the last cell and if it's an unsafe cell (clashing)

        if (b[y] < 8) { //We found a safe cell. Hooray!

            if (y < 7) { //Did we place the last queen?
                b[++y] = -1; //Nope, let's allocate the next one.
            } else {
                putboard(); //Yup, let's print the result!
            }

        } else { //If not a single safe cell was found, we reallocate the last queen.
            y--;
        }
    }
}

On the first while, you're going to iterate through each cell in a row (or column, however you prefer it. It's just a rotation matter). On each cell you make the unsafe(y) check, which will return true in case the cell you're placing the queen in is clashing with other queen-occupied cells (as you've already found out in the comment).

Next step, once we've found a safe cell in which to place the actual queen (y), we make a security check: if we have not found a single safe cell for that queen, we have to reallocate last queen.

In case the cell was found and was correct, we check whether it was the last queen (y < 7). If it is so, we proceed to print the result. Otherwise, we just re-start the while loop by placing b[++y] = -1.

Unsafe function:

public static boolean unsafe(int y) {
    int x = b[y]; //Let's call the actual cell "x"
    for (int i = 1; i <= y; i++) { //For each queen before placed BEFORE the actual one, we gotta check if it's in the same row, column or diagonal.
        int t = b[y - i];
        if (t == x || t == x - i || t == x + i) {
            return true; //Uh oh, clash!
        }
    }
    return false; //Yay, no clashes!
}

This function checks whether the queen we're using clashes with any of the allocated queens before this one. The clashes might happen diagonally, vertically or horizontally: That is why there is a triple OR check before the "return true" statement.

Putboard function:

public static void putboard() {
    System.out.println("

Solution " + (++s));
    for (int y = 0; y < 8; y++) {
        for (int x = 0; x < 8; x++) {
            if (b[y] == x)
                System.out.print("|Q");
            else
                System.out.print("|_");
        }
        System.out.println("|");
    }
}

I'm not gonna explain this one that deep, because it is simply a fairly simply line printing function which you can find out how it works by yourself when executing the solution!

Hope this helps.

Cheers!


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...