// NQueens.java
// Krzysztof Kuchcinski and Radoslaw Szymanek, 2008
// Slightly modified by Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/* Place n queens on a n x n chessboard
   so none of the queens are in check.

   Example of queens placement on a 4x4 chessboard
        ---------
        | | |Q| |
        ---------
        |Q| | | |
        ---------
        | | | |Q|
        ---------
        | |Q| | |
        ---------

   More info:   https://en.wikipedia.org/wiki/Eight_queens_puzzle

   There are no solutions for orders 1, 2 and 3 and, ignoring 
   rotations and reflections, only one basic solution for order four, 
   two basic solutions for order five, one for order six, six for order
   seven and twelve for order eight. 

   To derive all the solutions it's necessary to consider the four 
   rotations of each pattern and their left-to-right mirror images.

    n 	basic 	all
    1 	1 		1
    2 	0 		0
    3 	0 		0
    4 	1 		2
    5 	2 		10
    6 	1 		4
    7 	6 		40
    8 	12 		92
    9 	46 		352
    10 	92 		724 


  Usage:
     > compile NQueens.java
     > run NQueens [<no. of sides>]
    e.g.
     > run NQueens
     No. of queens = 4
     No. of Solutions: 2
     1. Q1 = 2;  Q2 = 4;  Q3 = 1;  Q4 = 3;
     2. Q1 = 3;  Q2 = 1;  Q3 = 4;  Q4 = 2;

     > run NQueens 5
     No. of queens = 5
     No. of Solutions: 10
     1. Q1 = 1;  Q2 = 3;  Q3 = 5;  Q4 = 2;  Q5 = 4;
     2. Q1 = 1;  Q2 = 4;  Q3 = 2;  Q4 = 5;  Q5 = 3;
     3. Q1 = 2;  Q2 = 4;  Q3 = 1;  Q4 = 3;  Q5 = 5;
     4. Q1 = 2;  Q2 = 5;  Q3 = 3;  Q4 = 1;  Q5 = 4;
     5. Q1 = 3;  Q2 = 1;  Q3 = 4;  Q4 = 2;  Q5 = 5;
     6. Q1 = 3;  Q2 = 5;  Q3 = 2;  Q4 = 4;  Q5 = 1;
     7. Q1 = 4;  Q2 = 1;  Q3 = 3;  Q4 = 5;  Q5 = 2;
     8. Q1 = 4;  Q2 = 2;  Q3 = 5;  Q4 = 3;  Q5 = 1;
     9. Q1 = 5;  Q2 = 2;  Q3 = 4;  Q4 = 1;  Q5 = 3;
     10. Q1 = 5;  Q2 = 3;  Q3 = 1;  Q4 = 4;  Q5 = 2;
*/

import org.jacop.constraints.*;
import org.jacop.core.*;
import org.jacop.search.*;
  // uses Jacop: https://jacop.cs.lth.se/

import java.util.*;


public class NQueens
{
  private static final int NUM_QUEENS = 4;

  public static void main(String args[])
  {
    int numQs = NUM_QUEENS;
    if (args.length != 0)
      numQs = Integer.parseInt(args[0]);
    System.out.println("No. of queens = " + numQs);

    Store store = new Store();

    // create constraint variables
    IntVar queens[] = new IntVar[numQs];
    for (int i = 0; i < numQs; i++)
      queens[i] = new IntVar(store, "Q" + (i + 1), 1, numQs);
    store.impose(new Alldifferent(queens));

    // constrain diagonals
    IntVar[] diagonalUp = new IntVar[queens.length];
    IntVar[] diagonalDown = new IntVar[queens.length];

    diagonalUp[0] = queens[0];     // diagonal like this /
    diagonalDown[0] = queens[0];     // diagonal like this \

    for (int i = 1; i < queens.length; i++) {
      diagonalUp[i] = new IntVar(store, -2*numQs, 2*numQs);
      store.impose(new XplusCeqZ(queens[i], i, diagonalUp[i]));

      diagonalDown[i] = new IntVar(store, -2*numQs, 2*numQs);
      store.impose(new XplusCeqZ(queens[i], -i, diagonalDown[i]));
    }

    store.impose(new Alldifferent(diagonalUp));
    store.impose(new Alldifferent(diagonalDown));

    SelectChoicePoint<IntVar> select = 
       new SimpleSelect<>(queens, null, new IndomainMin<>());

    Search<IntVar> search = new DepthFirstSearch<>();
    search.setPrintInfo(false);
    search.getSolutionListener().searchAll(true);    // get all answers
    search.getSolutionListener().recordSolutions(true);

    search.labeling(store, select);
    JacopUtils.printSolns(search);
  } /* main */

}  // end of NQueens class