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

/* A Latin Square Solver
   https://en.wikipedia.org/wiki/Latin_square

   LatinSquare problem consists of filling the square
   of size by size with numbers 1..size 
   in such a way that every row and column does 
   not contain two numbers with the same value.

  Usage:
     > compile LatinSquare.java
     > run LatinSquare [ <size> ]
     e.g.
     > run LatinSquare
     Latin square size = 5x5
     Square values:
      1  2  3  4  5
      2  5  1  3  4
      3  1  4  5  2
      4  3  5  2  1
      5  4  2  1  3

     > run LatinSquare 7
     Latin square size = 7x7
     Square values:
      1  2  3  4  5  6  7
      2  7  1  3  4  5  6
      3  1  6  7  2  4  5
      4  3  5  2  6  7  1
      5  4  2  6  7  1  3
      6  5  7  1  3  2  4
      7  6  4  5  1  3  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 LatinSquare
{
  private static final int LATIN_SIZE = 5;


  public static void main(String args[])
  {
    int size = LATIN_SIZE;
    if (args.length != 0)
      size = Integer.parseInt(args[0]);
    System.out.println("Latin square size = " + size + "x" + size);

    Store store = new Store();

    // create constraint variables
    IntVar[][] lsqr = new IntVar[size][size];
    for (int i = 0; i < size; i++)
      for (int j = 0; j < size; j++) {
        lsqr[i][j] = new IntVar(store, "lsqr" + i + "_" + j, 1, size);
      }

    // Create row and column constraints
    for (int i = 0; i < size; i++) {
      store.impose(new Alldifferent(lsqr[i]));   // constraint on row i
      IntVar[] y = new IntVar[size];
      for (int j = 0; j < size; j++)
        y[j] = lsqr[j][i];   // using i as column index
      store.impose(new Alldifferent(y));  // constraint on column i
    }

    SelectChoicePoint<IntVar> select =
      new SimpleSelect<>( JacopUtils.toArray(lsqr),    // 2D --> 1D
                         new SmallestDomain<>(), new IndomainMin<>());

    Search<IntVar> search = new DepthFirstSearch<>();
    search.setPrintInfo(false);
    search.labeling(store, select);

    //JacopUtils.printSolns(search);
    System.out.println("Square values:");
    JacopUtils.printGrid(lsqr);
  } /* main */

}  // end of latinSquares class