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

/* Solves Kakuro puzzles.
   https://en.wikipedia.org/wiki/Kakuro

  Modify the rowVals and colVals arrays, and the NUM_ROWS and
  NUM_COLS constants to solve other puzzles.

  Insert a digit from 1 to 9 into each '1' cell so that the sum of 
  the numbers in each row/column matches the row/column total.
  Also, no digit can appear twice in any row/column entry.

  This solver doesn't allow a row and column total to appear together
  on one cell.

  Usage:
     > compile Kakuro.java
     > run Kakuro
     
     Grid values:
      0  0  0  0
      0  1  2  0
      0  3  1  2
      0  0  4  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 Kakuro
{
  private static final int NUM_ROWS = 4;
  private static final int NUM_COLS = 4;

  // >1 = wall with a row sum; <0 = wall with a column sum
  // 1 = an empty cell; 0 = solid wall
  private static final int[][] rowVals = {
    {0, 0, 0, 0},
    {3, 1, 1, 0},
    {6, 1, 1, 1},
    {0, 5, 1, 1}
  };

  private static final int[][] columnVals = {
    {0, -4, -7,  0},
    {0,  1,  1, -3},
    {0,  1,  1,  1},
    {0,  0,  1,  1}
  };


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

    IntVar zero = new IntVar(store, "0", 0, 0);

    // create grid constraint variables
    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 (rowVals[i][j] == 1) {
          if (columnVals[i][j] != 1)
            System.out.println("Contradiction between row and column descriptions.");
          grid[i][j] = new IntVar(store, "grid" + i + "-" + j, 1, 9);
        }
        else
          grid[i][j] = zero;
      }
    }

    // Constraints for the rows
    for (int i = 0; i < NUM_ROWS; i++) {
      for (int j = 0; j < NUM_COLS; j++) {
        if (rowVals[i][j] > 1) {   // found a row sum
          IntVar sum = new IntVar(store, "sumRow" + i + "-" + j,
                           rowVals[i][j], rowVals[i][j]);

          List<IntVar> row = new ArrayList<>();
          for (int m = j + 1; m < NUM_COLS && rowVals[i][m] == 1; m++)
            row.add(grid[i][m]);   // collect row sums in list

          store.impose(new SumInt(row, "==", sum));  
                      // summation constraint with sum at start of row
          store.impose(new Alldiff(row));  
                    // adds bounds consistency to Alldifferent()
        }
      }
    }

    // Constraints for the columns
    for (int i = 0; i < NUM_ROWS; i++) {
      for (int j = 0; j < NUM_COLS; j++) {
        if (columnVals[i][j] < 0) {   // found a column sum (which is -ve)
          IntVar sum = new IntVar(store, "sumCol" + i + "-" + j,
                    -columnVals[i][j], -columnVals[i][j]);
                      // make negative column sums positive
          List<IntVar> column = new ArrayList<>();
          for (int m = i + 1; m < NUM_ROWS && columnVals[m][j] == 1; m++)
            column.add(grid[m][j]);  // collect column sums in list

          store.impose(new SumInt(column, "==", sum));
                      // summation constraint with sum at start of row
          store.impose(new Alldiff(column));
        }
      }
    }

    SelectChoicePoint<IntVar> select =
      new SimpleSelect<>( JacopUtils.toArray(grid),    // 2D --> 1D
                         null, 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 Kakuro class