N * N queen algorithm getting the coordinates

问题:

I'm trying to implement the N*N queen algorithm with a little twist to it. In this version the queen can also move like a knight...

Everything is working fine, but I'm trying to get the coordinates of all the possible solutions. The problem is that if I put it inside col == n it just prints the last one. Any ideas of how to solve this?

  static void placement(int col, int queens[], int n){
    //int solution =0; 
    for (int row = 1; row <= n; row++) {
      queens[col] = row;
      if((check_Queen(row,col,queens)) ==  true)
      {
        if((check_KnightMove(row,col,queens)) == true)
        {
          if(col == n)
          {
            System.out.println("("+row + "," + col);
            System.out.println("solution=" + solution);
            solution++;
          }
          else
          { 
            placement(col+1,queens,n);   
          }
        }
      }
    }
    queens[col] = 0;
  }

  public static void main(String[] args) {
    int solution =0;
    Scanner scanner=new Scanner(System.in);
    System.out.print("Please enter N");
    int n = scanner.nextInt();// TODO Auto-generated method stub
    int queens[] = new int[n+1];
    placement(1,queens,n);
    System.out.println("nQueens: solution=" + solution);
  }
      static boolean check_Queen(int row, int col, int queens[])
{

    //boolean flag = false;
    for(int i =1; i<col; i++)
    {
        if (queens[col-i] == row   ||
                 queens[col-i] == row-i ||
                 queens[col-i] == row+i) {
                //flag = false;
                return false;
             }

    }
    return true;


}
           static boolean  check_KnightMove(int row, int col, int queens[])
           {
    if(col>=2&&(queens[col-2] == (row -1) || queens[col-2] == (row+1) || queens[col-1] == (row-2) || queens[col-1] == (row+2)))
    {
        return false;
    }
    return true;

}


}

回答1:

It is hard to tell what is wrong in your solution without knowing how check_Queen and check_KnightMove are defined. Here is how I would solve the task:

public class Queens
{
    static void printSolution (int [] queens)
    {
        int l = queens.length;
        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < l; j++)
            {
                System.out.print (queens [i] == j ? 'Q' : '.');
                System.out.print (' ');
            }
            System.out.println ();
        }
        System.out.println ();
    }

    static int placement (int [] queens, int c)
    {
        if (c == queens.length)
        {
            printSolution (queens);
            return 1;
        }
        else
        {
            int solutionCount = 0;
            int l = queens.length;

            for (int r = 0; r < l; r++)
            {
                boolean flag = false;
                for (int i = 0; i < c; i++)
                {
                    int xd = c - i;
                    int yd = Math.abs (r - queens [i]);

                    if (yd == 0 || xd == yd)
                    {
                        flag = true;
                        break;
                    }

                    // Knight move support
                    if ((xd == 1 && yd == 2) || (xd == 2 && yd == 1))
                    {
                        flag = true;
                        break;
                    }
                }

                if (!flag)
                {
                    queens [c] = r;
                    solutionCount += placement (queens, c + 1);
                }
            }

            return solutionCount;
        }
    }

    public static void main (String [] args)
    {
        System.out.println (
            "Total solutions found: " + placement (new int [11], 0));
    }
}

In your solution, method check_KnightMove is incorrect. When col == 2 it does not allow Queen to be placed at row 1, because it believes that there is always a Queen at (col: 0, row: 0), i.e. outside the board. Here is corrected version:

static boolean check_KnightMove (int row, int col, int queens[])
{
    if (col >= 3
            && (queens [col - 2] == (row - 1) || queens [col - 2] == (row + 1)))
    {
        return false;
    }

    if (col >= 2
            && (queens [col - 1] == (row - 2) || queens [col - 1] == (row + 2)))
    {
        return false;
    }
    return true;
}