java - 为什么从方法内部调用时方法回溯不起作用

Question

当我从其中第二次调用方法回溯(回溯)时，因为我需要返回两步，它不起作用。有人有什么主意吗？这是我的代码:

// width of board
static final int SQUARES = 8;

// board
static boolean[][] board = new boolean[SQUARES][SQUARES];

// represents values for number of squares eliminated if queen is placed in square
static int[][] elimination = new int[SQUARES][SQUARES];

// store position of queens
static boolean[][] position = new boolean[SQUARES][SQUARES];

// store row
static int[] row = new int[8];

// store column
static int[] column = new int[8];

// Write a program to solve the Eight Queens problem
public static void main(String[] args)
{
    Arrays.fill(row, -1);
    Arrays.fill(column, -1);

    // reset elimination table
    fillElim();

    // count queens on board
    short counter = 0;

    // while board is not full
    while(counter < 8) {
        // place next queen on board
        placeQueen(-1, -1);

        // reset elimination table
        fillElim();

        // backtrack and fill board back to this point
        while(isFull() && counter < 7)
            backtrack(counter);

        counter++;

    }   // end while

    System.out.println("Queens on board: " + counter);
    printBoard();

    for(int i = 0; i < row.length; i++)
        System.out.println(column[i] + "/" + row[i]);

}   // end method main

// Print elimination table
public static void printE()
{
    for(int i[] : elimination) {
        for(int j = 0; j < i.length; j++)
            System.out.printf("%-3d", i[j]);

        System.out.println();

    }   // end for
}   // end printE

public static void printBoard()
{
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board.length; j++) {

            if(board[i][j] && position[i][j])
                System.out.print("o ");
            else if(board[i][j])
                System.out.print("x ");
            else
                System.out.print("% ");

        }   // end inner for

        System.out.println();

    }   // end outer for
}   // end method printBoard

// Write method to calculate how many squares are eliminated if queen is placed in that square
public static void fillElim()
{
    // if any squares that could be eliminated already are eliminated, subtract 1
    for(int i = 0; i < elimination.length; i++) {
        for(int j = 0; j < elimination[i].length; j++) {

            elimination[i][j] = openSquares(i, j);

        }   // end inner for
    }   // end outer for
}   // end method fillElimination

// Number of squares eliminatable by placing queen in any given square
public static int openSquares(int row, int column)
{
    // if square is already eliminated, it cannot be used
    if(board[row][column])
        return 0;

    // total number of squares elimintable from any given square, count square itself
    int total = 1 + openHorizontal(row) + openVertical(column) + openUpSlope(row, column) + openDownSlope(row, column);

    return total;
}   // end method openSquares

// Return number of open squares in a row
public static int openHorizontal(int row)
{
    // total of row
    int total = 0;

    for(boolean b : board[row]) {

        // if square is "true" (open), increment total open squares
        if(!b)
            total++;

    }   // end for

    // return total not counting current square
    return total - 1;

}   // end method openHorizontal

// Return number of open squares in a column
public static int openVertical(int column)
{
    // total of column
    int total = 0;

    // if square is "true" (open), increment total open squares
    for(boolean[] b : board) {

        // if square is "true" (open), increment total open square
        if(!b[column])
            total++;

    }   // end for

    // return total not counting current square
    return total - 1;

}   // end method openVertical

// Return number of open squares in a column
public static int openDownSlope(int x, int y)
{
    // total of downward-sloping diagonal
    int total = 0;

    // if square is "true" (open), increment total open squares
    for(int i = 0; i < board.length; i++) {

        // test all values before use to prevent array index errors
        // all squares to the top right of the checking square
        if(x+i >= 0 && x+i < board.length && y+i >= 0 && y+i < board.length) {

            // else increment total
            if(!board[x+i][y+i])
                total++;

        }   // end if

        // all squares to the bottom left of the checking square
        if(x-i >= 0 && x-i < board.length && y-i >= 0 && y-i < board.length) {

            // else increment total
            if(!board[x-i][y-i])
                total++;

        }   // end if
    }   // end for

    // return total not counting current square
    return total - 2;

}   // end method openDownSlope

// Return number of open squares in a column
public static int openUpSlope(int x, int y)
{
    // total of upward-sloping diagonal
    int total = 0;

    // if square is "true" (open), increment total open squares
    for(int i = 0; i < board.length; i++) {

        // test all values before use to prevent array index errors
        // all squares to the top right of the checking square
        if(x+i >= 0 && x+i < board.length && y-i >= 0 && y-i < board.length) {

            // else increment total
            if(!board[x+i][y-i])
                total++;

        }   // end if

        // all squares to the bottom left of the checking square
        if(x-i >= 0 && x-i < board.length && y+i >= 0 && y+i < board.length) {

            // else increment total
            if(!board[x-i][y+i])
                total++;

        }   // end if
    }   // end for

    // return total not counting current square
    return total - 2;

}   // end method openDownSlope

// Are all squares on the board filled?
public static boolean isFull()
{
    for(boolean b[] : board) {
        for(boolean bb : b) {

            if(!bb)
                return false;

        }   // end inner for
    }   // end outer for

    // if this point is reached, board is full
    return true;

}   // end method isFull

// Place a queen on the board
public static void placeQueen(int lastRow, int lastCol)
{
    int[] bestSquare = bestMove(lastRow, lastCol);

    System.out.println("&&&&&&");

    for(int i = 0; i < row.length; i++)
        System.out.println(row[i] + "/" + column[i]);

    System.out.println("&&&&&&");

    // assign queen to board
    board[bestSquare[0]][bestSquare[1]] = true;

    printBoard();
    System.out.println();

    // clear blocked squares from board
    elimSquares(bestSquare[0], bestSquare[1]);

    // reset elimination table
    fillElim();

    // store squares
    for(int i = 0; i < row.length; i++) {

        if(row[i] == -1) {
            row[i] = bestSquare[0];
            column[i] = bestSquare[1];
            break;

        }   // end if
    }   // end for

    // mark queen's position
    position[bestSquare[0]][bestSquare[1]] = true;

    printBoard();

}   // end method placeQueen

// Return lowest number in elimination table
public static int[] bestMove(int lastRow, int lastCol)
{
    // store lowest number - set to impossibly low
    int low = 100;

    // store coordinates
    int[] move = {-1, -1};

    // store limit of use
    int limit;

    if(lastRow == -1)
        limit = 0;
    else
        limit = elimination[lastRow][lastCol];

    // if lastRow is not -1, search for duplicate numbers after current square
    if(lastRow != -1) {

        // test for equal elimination numbers farther down on board
        for(int i = lastRow; i < board.length; i++) {
            for(int j = lastCol+1; j < board[i].length; j++) {

                if(!board[i][j] && elimination[i][j] == limit) {
                    move[0] = i;
                    move[1] = j;
                    return move;
                }

            }   // end inner for
        }   // end outer for
    }   // end if

    // test for any available squares left on board
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[i].length; j++) {

            if(!board[i][j] && elimination[i][j] > limit && elimination[i][j] < low)
                low = elimination[i][j];

        }   // end inner for
    }   // end outer for

    // get move coordinates for square, if needed to get best square after two backtracks
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[i].length; j++) {

            if(!board[i][j] && elimination[i][j] == low) {

                move[0] = i;
                move[1] = j;
                return move;

            }   // end if
        }   // end inner for
    }   // end outer for

    return move;

}   // end method bestMove

public static void elimSquares(int row, int column)
{
    // total number of squares elimintable from any given square, count square itself
    elimHorizontal(row);
    elimVertical(column);
    elimUpSlope(row, column);
    elimDownSlope(row, column);

}   // end method openSquares

// Eliminate row
public static void elimHorizontal(int row)
{
    // eliminate row
    for (int i = 0; i < board[row].length; i++)
        board[row][i] = true;

}   // end method elimHorizontal

// Eliminate column
public static void elimVertical(int column)
{
    // eliminate column
    for(boolean[] b : board)
        b[column] = true;

}   // end method elimVertical

// Eliminate downward slope
public static void elimDownSlope(int x, int y)
{
    // loop through downward slope
    for(int i = 0; i < board.length; i++) {

        // test all values before use to prevent array index errors

        // eliminate all squares to the bottom right of the checking square
        if(x+i >= 0 && x+i < board.length && y+i >= 0 && y+i < board.length)
            board[x+i][y+i] = true;

        // eliminate all squares to the top left of the checking square
        if(x-i >= 0 && x-i < board.length && y-i >= 0 && y-i < board.length)
            board[x-i][y-i] = true;

    }   // end for
}   // end method elimDownSlope

// Eliminate upward slope
public static void elimUpSlope(int x, int y)
{
    // loop through upward slope
    for(int i = 0; i < board.length; i++) {

        // test all values before use to prevent array index errors

        // eliminate all squares to the bottom right of the checking square
        if(x+i >= 0 && x+i < board.length && y-i >= 0 && y-i < board.length)
            board[x+i][y-i] = true;

        // eliminate all squares to the top left of the checking square
        if(x-i >= 0 && x-i < board.length && y+i >= 0 && y+i < board.length)
            board[x-i][y+i] = true;

    }   // end for
}   // end method elimDownSlope

// If not found solution and board is full
public static void backtrack(int lastMove)
{
    // store last move
    int lastRow = row[lastMove];
    int lastCol = column[lastMove];

    // clear board
    resetBoard();

    // go back 1 move
    goBack(lastMove);

    // refill board
    for(int i = 0; i < row.length; i++) {

        // escape if out of bounds
        if(row[i] == -1)
            break;

        // replace queens
        board[row[i]][column[i]] = true;

        // fill elimination table
        elimSquares(row[i], column[i]);

    }   // end for

    // while no open squares, go back one more row
    // keep track of times looped
    int counter = 0;

    while(!openSpaces(lastRow, lastCol)) {
        System.out.println("backtrack " + counter);
        backtrack(lastMove-1);
        counter++;
    }   // end while

    // set queen in square
    placeQueen(lastRow, lastCol);

}   // end method backtrack

// Clear board
public static void resetBoard()
{
    // clear board
    for(boolean[] b : board)
        for(int j = 0; j < b.length; j++)
            b[j] = false;

}   // end method resetBoard

// Go back 1 move
public static void goBack(int lastMove)
{
    // remove queen from last position
    position[row[lastMove]][column[lastMove]] = false;

    // remove last move from table
    row[lastMove] = -1;
    column[lastMove] = -1;

}   // end method goBack

// Return number of open, untested spaces on board
public static boolean openSpaces(int lastRow, int lastCol)
{
    // store number of open, untested squares
    int squares = 0;

    // store limit of use
    int limit = elimination[lastRow][lastCol];

    // store next limit for use if no more squares at limit
    int nextLimit = limit + 1;

    // test for equal elimination numbers farther down on board
    for(int i = lastRow; i < board.length; i++) {
        for(int j = lastCol+1; j < board[i].length; j++) {

            if(!board[i][j] && elimination[i][j] == limit)
                squares++;

        }   // end inner for
    }   // end outer for

    // test for any available squares left on board
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[i].length; j++) {

            if(!board[i][j] && elimination[i][j] >= nextLimit)
                squares++;

        }   // end inner for
    }   // end outer for

    return squares != 0;

}   // end method openSpaces

这会调用方法 goBack； placeQueen 方法，调用 bestMove 方法；和其他一些。这三个方法也可能有错误，我不确定:

// Go back 1 move
public static void goBack(int lastMove)
{
    // remove queen from last position
    position[row[lastMove]][column[lastMove]] = false;

    // remove last move from table
    row[lastMove] = -1;
    column[lastMove] = -1;

}   // end method goBack

// Place a queen on the board
public static void placeQueen(int lastRow, int lastCol)
{
    int[] bestSquare = bestMove(lastRow, lastCol);

    System.out.println("&&&&&&");

    for(int i = 0; i < row.length; i++)
        System.out.println(row[i] + "/" + column[i]);

    System.out.println("&&&&&&");

    // assign queen to board
    board[bestSquare[0]][bestSquare[1]] = true;

    printBoard();
    System.out.println();

    // clear blocked squares from board
    elimSquares(bestSquare[0], bestSquare[1]);

    // reset elimination table
    fillElim();

    // store squares
    for(int i = 0; i < row.length; i++) {

        if(row[i] == -1) {
            row[i] = bestSquare[0];
            column[i] = bestSquare[1];
            break;

        }   // end if
    }   // end for

    // mark queen's position
    position[bestSquare[0]][bestSquare[1]] = true;

    printBoard();

}   // end method placeQueen

// Return lowest number in elimination table
public static int[] bestMove(int lastRow, int lastCol)
{
    // store lowest number - set to impossibly low
    int low = 100;

    // store coordinates
    int[] move = {-1, -1};

    // store limit of use
    int limit;

    if(lastRow == -1)
        limit = 0;
    else
        limit = elimination[lastRow][lastCol];

    // if lastRow is not -1, search for duplicate numbers after current square
    if(lastRow != -1) {

        // test for equal elimination numbers farther down on board
        for(int i = lastRow; i < board.length; i++) {
            for(int j = lastCol+1; j < board[i].length; j++) {

                if(!board[i][j] && elimination[i][j] == limit) {
                    move[0] = i;
                    move[1] = j;
                    return move;
                }

            }   // end inner for
        }   // end outer for
    }   // end if

    // test for any available squares left on board
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[i].length; j++) {

            if(!board[i][j] && elimination[i][j] > limit && elimination[i][j] < low)
                low = elimination[i][j];

        }   // end inner for
    }   // end outer for

    // get move coordinates for square, if needed to get best square after two backtracks
    for(int i = 0; i < board.length; i++) {
        for(int j = 0; j < board[i].length; j++) {

            if(!board[i][j] && elimination[i][j] == low) {

                move[0] = i;
                move[1] = j;
                return move;

            }   // end if
        }   // end inner for
    }   // end outer for

    return move;

}   // end method bestMove

我认为 placeQueen 在回溯方法中的回溯之前以某种方式被调用。

附注这与 https://stackoverflow.com/questions/20111154/use-elimination-heuristic-to-solve-eight-queens-puzzle 不是同一个问题。在那里我问我需要做什么；在这里我想问为什么我的方法不起作用。

Answer 1

顺便说一句。解决皇后问题的更简单方法。该程序将打印出所有 92 个解决方案。

public class Queens {
    static int counter = 0;
    static int[] pos = new int[8];

    static void printBoard(){
        for(int p: pos) {
            for(int i = 0; i < p; i++) System.out.print(".");
            System.out.print("Q");
            for(int i = p+1; i < 8; i++) System.out.print(".");
            System.out.println();
        }
        System.out.println();
    }

    static boolean threatened(int x, int y){
        for (int i = 0; i < y; i++){
            int d = y - i;
            if(pos[i] == x || pos[i] == x - d || pos[i] == x + d) {
                return true;
            }
        }
        return false;
    }

    static void place(int y) {
        for(int x = 0; x < pos.length ; x++){
            if(!threatened(x, y)){
                pos[y] = x;
                if(y == 7){
                    printBoard();
                    counter++;
                } else{
                    place(y + 1);
                }
            }
        }
    }

    public static void main(String[] args){
        place(0);
        System.out.print("found " + counter + " solutions");
    }
}