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

/* Sudoku Solver
   More Info:   https://en.wikipedia.org/wiki/Sudoku

  Modify the vals array to solve other puzzles.

  Usage:
     > compile Sudoku.java
     > run Sudoku

     Grid values:
      8  1  3  4  2  9  7  6  5
      4  6  2  5  7  1  8  3  9
      7  9  5  3  6  8  1  4  2
      2  4  7  1  5  3  9  8  6
      5  3  9  8  4  6  2  1  7
      6  8  1  2  9  7  4  5  3
      9  7  8  6  1  5  3  2  4
      1  2  6  7  3  4  5  9  8
      3  5  4  9  8  2  6  7  1
*/

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

import java.util.*;


public class Sudoku
{
  // No of rows and columns in terms of boxes
  private static final int BOX_ROWS = 3;
  private static final int BOX_COLS = 3;
  private static final int BOX_SZ = 3;

  private static final int NUM_ROWS = BOX_ROWS*BOX_SZ;
  private static final int NUM_COLS = BOX_COLS*BOX_SZ;

    // 0 - unknown element
  private static final int[][] vals = {
      {0, 1, 0, 4, 2, 0, 0, 0, 5},   // 0 == unknown value
      {0, 0, 2, 0, 7, 1, 0, 3, 9},
      {0, 0, 0, 0, 0, 0, 0, 4, 0},
      {2, 0, 7, 1, 0, 0, 0, 0, 6},
      {0, 0, 0, 0, 4, 0, 0, 0, 0},
      {6, 0, 0, 0, 0, 7, 4, 0, 3},
      {0, 7, 0, 0, 0, 0, 0, 0, 0},
      {1, 2, 0, 7, 3, 0, 5, 0, 0},
      {3, 0, 0, 0, 8, 2, 0, 7, 0}
    };


  public static void main(String args[])
  {
    Store store = new Store();

    // create constraint variables for the grid
    IntVar[][] grid = new IntVar[NUM_ROWS][NUM_COLS];
    for (int i = 0; i < NUM_ROWS; i++) {
      for (int j = 0; j < NUM_COLS; j++) {
        if (vals[i][j] == 0)   // unknown value
          grid[i][j] = new IntVar(store, "g" + i + j, 1, BOX_SZ*BOX_SZ);
        else  // value is fixed
          grid[i][j] = new IntVar(store, "g" + i + j, vals[i][j], vals[i][j]);
      }
    }

    // Constraints for rows
    for (int i = 0; i < NUM_ROWS; i++)
      store.impose(new Alldistinct(grid[i]));  // fancy Alldifferent()

    // Constraints for columns
    for (int j = 0; j < NUM_COLS; j++) {
      IntVar[] column = new IntVar[NUM_ROWS];
      for (int i = 0; i < NUM_ROWS; i++)
        column[i] = grid[i][j];
      store.impose(new Alldistinct(column));
    }

    // Constraints for boxes
    for (int i = 0; i < BOX_ROWS; i++) {
      for (int j = 0; j < BOX_COLS; j++) {
        List<IntVar> block = new ArrayList<IntVar>();
        for (int k = 0; k < BOX_SZ; k++) {
          for (int m = 0; m < BOX_SZ; m++)
            block.add(grid[i*BOX_SZ + k][j*BOX_SZ + m]);
        }
        store.impose(new Alldistinct(block));
      }
    }

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

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

    // JacopUtils.printSolns(search);
    System.out.println("Grid values:");
    JacopUtils.printGrid(grid);

  } /* main */


}  // end of Sudoku class