java - 我的 NQueens isSafeMove() 函数不断返回 false

Question

我的 NQueens isSafeMove() 函数不断返回 false，我不明白为什么。我相信这可能与我的 checkLeft、checkUpperDiag 或 checkLowerDiag 有关，但我认为它们没有任何问题。 isSafeMove 检查是否是皇后任意可移动距离内的棋子，如果有则返回 false，如果没有则返回 true。

import java.awt.Point;
public class NQueensModel 
{
    private int myNumQueens;
    private boolean myBoard[][];
    private boolean mySolutionBoard [][];
    private String mySolutionBoardString [][];
    private int myNumSolutions;


NQueensModel(int nQueens)
{
    myNumQueens = nQueens;
    myBoard = new boolean [myNumQueens][myNumQueens];
    mySolutionBoard = new boolean [myNumQueens][myNumQueens];
    mySolutionBoardString = new String [myNumQueens][myNumQueens];
}

public boolean solvePuzzle()
{
    return solvePuzzle(0);
}

private boolean solvePuzzle(int ncolumn)
{
    if (ncolumn >= myNumQueens)
    {
        return true;
    }
    for(int i = 0; i < myNumQueens; i++)
    {
        if(this.isSafeMove(i, ncolumn) == true)
        {
            this.placeQueen(i, ncolumn);
            if(this.solvePuzzle(ncolumn + 1) == true)
            {
                return true;
            }
            this.removeQueen(i, ncolumn);
        }
    }
    return false;
}

public boolean isSafeMove(int row, int col)
{
    if(this.checkLeft(row, col) || this.checkUpperDiag(row, col)
            || this.checkLowerDiag(row, col) == true)
    {
        System.out.println("false");
        return false;
    }

    else 
    {
        System.out.println("true");
        return true;
    }
}

private boolean checkLeft(int row, int col)
{

    if(col >= myNumQueens || row >= myNumQueens)
    {
        return false;
    }
    if(row == 0)
    {
        return true;
    }
    for(int i= col - 1 ; i >= 0; i--)
    {
        if(myBoard[row][i] == true)
        {
            return false;
        }
        if(i == 0)
        {
            return true;
        }
    }
    return false;
}

private boolean checkUpperDiag(int row, int col)
{
    if(col == 0 || row == 0)
    {
        return true;
    }
    for(int i = row, j = col; row >= 0 || col >= 0; row--, col--)
    {
        if(myBoard[row][col] == true)
        {
            return false;
        }
        if(col == 0 && row == 0)
        {
            return true;
        }
    }
    return false;
}

private boolean checkLowerDiag(int row, int col)
{
    if(col == 0 || row == myNumQueens - 1)
    {
        return true;
    }
    for(int i = row, j = col; row < myNumQueens || col < myNumQueens; row--, col++)
    {
        if(myBoard[row][col] == true)
        {
            return false;
        }
        if(col == 0 && row == myNumQueens - 1)
        {
            return true;
        }
    }

    return false;
}



public boolean placeQueen(int row, int col)
{
    if(myBoard[row][col] == false)
    {
        myBoard[row][col] = true;
        return false;
    }
    return false;
}


public String getMySolutionBoardString()
{
    for(int col = 0; col < myNumQueens; col++)
    {
        for(int row = 0; row < myNumQueens; row++)
        {
            if(myBoard[col][row] == true)
            {
                mySolutionBoardString[row][col] = "Q";
            }
            else
            {
                mySolutionBoardString[row][col] = "-";
            }
            System.out.print(mySolutionBoardString[row][col] + " ");
        }
        System.out.println("");
    }
    return null;
}

private boolean removeQueen(int row, int col)
{
    myBoard[row][col] = false;
    return false;
}

public boolean getQueenOnBoard(Point point)
{
    return myBoard[(int)point.getX()][(int)point.getY()];
}

public String toString()
{
    String string = this.getMySolutionBoardString();
    return string;
}

}

Answer 1

在你的循环中

for(int i = 0; i < myNumQueens; i++)
{
    if(this.isSafeMove(i, ncolumn) == true)
    {
        this.placeQueen(i, ncolumn);
        if(this.solvePuzzle(ncolumn + 1) == true)
        {
            return true;
        }
        this.removeQueen(i, ncolumn);
    }
}

考虑一下，当您第一次调用 isSafeMove (i,ncolumn) 时，i = 0，因此 checkLeft 将返回 true，并且 ncolumn = 0 之后的每次迭代，因此您对 checkUpperDiag () 和 checkLowerDiag () 的调用将返回 true，因此这些方法每次返回 true 意味着 isSafeMove 将在循环的每次迭代中返回 false