0

所以下面的代码是一个 NQueens 程序，它给出了 NQueens 是否可以使用给定变量的正确真或假返回（即，如果它是 3，那么对于 3x3 板是否可行）。我遇到的麻烦是找出它有多少不同的可能性。例如，在 4x4 中，有 2 种可能性，所以它应该返回 true，（它已经这样做了）和 2。我不确定在哪里放置这个计数器方法或更改代码，以便它继续追求一种可能性。

有什么建议吗？

package model;

public class NQueensModel
{
    private int myNumsQueen;
    private int myPossibilities;
    private boolean[][] myBoard;
    private static NQueensModel myModel = new NQueensModel(4);

    public static void main (String[] args) {

        System.out.println(myModel.solvePuzzle());


    }
    public NQueensModel(int nQueens)
    {
        myNumsQueen = nQueens;
        myPossibilities=0;
        myBoard = new boolean[myNumsQueen][myNumsQueen];
    }
    public boolean solvePuzzle()
    {
        return this.solvePuzzle(0);
    }
    private boolean solvePuzzle(int ncolumn)
    {
        if(ncolumn>myNumsQueen-1)
        {

            return true;
        }
        int i;

        for( i =0; i<myNumsQueen;i++)
        {

            if(this.isSafeMove(i, ncolumn)==true)
            {

                this.placeQueen(i,ncolumn);
                System.out.println(i + " " + ncolumn);
                if(this.solvePuzzle(ncolumn+1)==true)
                {
                    return true;

                }
                this.removeQueen(i, ncolumn);
            }

        }

        return false;

    }
    private boolean isSafeMove(int row, int col)
    {

         if(this.checkLowerDiag(row, col)==true ||this.checkUpperDiag(row, col)==true ||this.checkLeft(row,col)==true)
         {
             return false;
         }
        else
        {

            return true;
        }


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

        if(col==0 )
        {           
            return false;             
        }
        else
        {

            for(int i = row, j = col; i<myNumsQueen && j>=0;  i++, j--)
            {
                if(myBoard[i][j]==true)
                {
                    return true;

                }


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

    }
    private boolean placeQueen(int row, int col)
    {
        myBoard[row][col] = true;
        return true;
    }
    private boolean removeQueen(int row, int col)
    {
        myBoard[row][col] = false;
        return false;
    }
//    public String toString()
//    {
//        
//    }
}
4

1 回答 1

0

下面是一种可能的解决方案的一些 sudo 代码。它会记录您迄今为止发现的所有有效解决方案。当发现新的解决方案时，将其添加到计数中并返回。这将完成，直到发现所有可能的解决方案。

public int solvePuzzle(int solutionCount, int col){
   if(isValidSolution())
      return solutionCount + 1;
   else if(solutionFails())
      return solutionCount;
   else {
      for(/*Every position you want to check in this col*/){
         solutionCount = solvePuzzle(solutionCount, col + 1);
      }
      return solutionCount;
   }
}
于 2013-11-06T20:35:31.897 回答