Courses/CS 460/Fall 2006/Nadeem, Hassan/Kakuro

From CSWiki

/*
To solve this problem i had to look at the example of kakuro. I understood the code 
and then implemented and modified the code using a 5x5 matrix. The idea is quite
 similiar as the 4x4 matrix kakuro code given in the example. The only difference is
 that 5x5 matrix is a little more complex than a 4x4. Also, this code is modified for
 Jacob 1.5. In order to run it in 2.1, you have to use search instead of searchOne.

Also i would like to suggest that the site http://puzzles.about.com/ 
have some easy kakuro puzzle which u can sove using Java to better understand 
how the program runs.
File uploaded on Tuesday. 
*/

import JaCoP.*;
import java.util.*;
import java.lang.*;

 public class Kakuro {

        public static void main(String args[]) {

    //Creating a 5*5 Matrix.
    //+ve and greater than 1 is the wall with row sum
    //-ve is column sum.
    //1=empty fields. Value to be determined.
    //0=empty wall.

                int[][] kakuroPuzzle = {{ 0, -11, -16, -12, -10}, { 12, 1, 1, 1, 1},
                                       { 10, 1, 1, 1, 1},{ 11, 1, 1, 1, 1 }, { 16, 1, 1, 1, 1 }};

                int numberofRows = 5;
                int numberofColumns = 5;

                FDstore store = new FDstore();
                FDV[][] elements = new FDV[numberofRows][numberofColumns];

                for (int i = 0; i < numberofRows; i++)
                for (int j = 0; j < numberofColumns; j++)
                        if (kakuroPuzzle[i][j] == 1)
                                elements[i][j] = new

                FDV(store, "f" + i + "-" + j, 1, 9);

                // Creating constraints for rows.
                for (int i = 0; i < numberofRows; i++)
                for (int j = 0; j < numberofColumns; j++)
                        if (kakuroPuzzle[i][j] > 1)
      {
        FDV sum = new FDV(store,"sumAt" + i + "-" + j,
        kakuroPuzzle[i][j], kakuroPuzzle[i][j]);

        ArrayList<FDV> row = new ArrayList<FDV>();

        for (int m = j + 1; m < numberofColumns && kakuroPuzzle[i][m] == 1;m++)
             {
                row.add(elements[i][m]);
             }
          store.impose(new Sum(row, sum));
          store.impose(new Alldiff(row));
      }

                // Creating constraints for columns.
                for (int i = 0; i < numberofRows; i++)
                for (int j = 0; j < numberofColumns; j++)
                        if (kakuroPuzzle[i][j] < 0)
                   {
                        FDV sum = new FDV(store, "sumCol" + i + "-" + j,
                                -kakuroPuzzle[i][j], -kakuroPuzzle[i][j]);

                ArrayList<FDV> column = new ArrayList<FDV>();

                for (int m = i + 1; m < numberofRows && kakuroPuzzle[m][j] == 1; m++)
                   {
                     column.add(elements[m][j]);
                   }
                store.impose(new Sum(column, sum));
                store.impose(new Alldiff(column));
                }

                ArrayList<FDV> fdvV = new ArrayList<FDV>();

                for (int i = 0; i < numberofRows; i++)
                for (int j = 0; j < numberofColumns; j++)
                        if (elements[i][j] != null)
                            {
                                fdvV.add(elements[i][j]);
                            }
                boolean result = Solver.searchOne(store, store, new SearchOne(), new IndomainMin(),new Delete(new MostConstrainedDynamic()));

                if (result)
                        System.out.println("Result " + fdvV);
                else
                        System.out.println("No solution");

        }
}