/**
 *
 * Minesweeper problem in Choco.
 *
 * This is a port of my MiniZinc and JaCoP models
 * http://www.hakank.org/minizinc/minesweeper.mzn
 * http://www.hakank.org/JaCoP/MineSweeper.java
 * 
 * which is commented in the (swedish) blog post
 * "Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life"
 * http://www.hakank.org/webblogg/archives/001231.html
 *
 * 
 * See also
 *  
 * The first 10 examples are from gecode/examples/minesweeper.cc
 * http://www.gecode.org/gecode-doc-latest/minesweeper_8cc-source.html
 *
 *
 * http://www.janko.at/Raetsel/Minesweeper/index.htm
 *
 * http://en.wikipedia.org/wiki/Minesweeper_(computer_game)
 * 
 * Ian Stewart on Minesweeper: http://www.claymath.org/Popular_Lectures/Minesweeper/
 *
 * Richard Kaye's Minesweeper Pages:
 * http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
 *
 * Some Minesweeper Configurations:
 * http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf
 *
 *
 *
 * choco model by Hakan Kjellerstrand (hakank@bonetmail.com)
 * Also see http://www.hakank.org/choco/
 *
 */


/*
 * Comparison with the MiniZinc model for the minesweeper_kaye_splitter.txt.
 * 
 * There are 131072 solutions.
 *
 * MiniZinc:
 * The Gecode/fz solver MiniZinc reports the following statistics:
 * with the solver annotations: "first_fail", "indomain", "complete".
 *
 *      runtime:       48620
 *      solutions:     131072
 *      propagators:   33
 *      propagations:  13209
 *      failures:      4
 *      clones:        131075
 *      commits:       342933
 *      peak memory:   148 KB
 *
 * Solving and printing one solution takes about 1 second.
 *
 *
 */


import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.model.CPModel.*;
import choco.cp.solver.CPSolver;
import choco.cp.solver.CPSolver.*;
import choco.cp.solver.constraints.*;
import choco.cp.solver.*;
import choco.kernel.model.variables.integer.*;
import choco.kernel.*;
import choco.kernel.solver.*;
import choco.kernel.model.*;
import choco.kernel.model.variables.*;
import choco.kernel.model.constraints.*;
import choco.kernel.model.variables.set.*;
import choco.cp.solver.search.integer.varselector.*;
import choco.cp.solver.search.integer.valiterator.*;
import choco.cp.solver.search.integer.valselector.*;
import choco.cp.solver.search.integer.branching.*;

import java.io.*;
import java.util.*;
import java.text.*;


public class MineSweeper {

    int r;        // number of rows
    int c;        // number of cols
    int X = -1;  // represents the unknown value in the problem matrix

    int[][] problem; // The problem matrix
    IntegerVariable[][] game;    // The IntegerVariable version of the problem matrix.
    IntegerVariable[][] mines;   // solution matrix: 0..1 where 1 means mine.

    Model model;
    CPSolver s;


    /**
     *
     * model()
     *
     */
    public void model() {

        model = new CPModel();

        if (problem == null) {

            //
            // This problem is from Gecode/examples/minesweeper.cc,  problem 1
            // (also as the file minesweeper1.txt)
            //
            r = 8;
            c = 8;
            int problemX[][] = {{X,2,X,2,1,1,X,X},
                                {X,X,4,X,2,X,X,2},
                                {2,X,X,2,X,X,3,X},
                                {2,X,2,2,X,3,X,3},
                                {X,X,1,X,X,X,4,X},
                                {1,X,X,X,2,X,X,3},
                                {X,2,X,2,2,X,3,X},
                                {1,X,1,X,X,1,X,1}};

            problem = problemX;

        }


        //
        // Initialize the constraint variables.
        //
        mines = new IntegerVariable[r][c];
        game  = new IntegerVariable[r][c];
        for(int i = 0; i < r; i++) {
            mines[i] = makeIntVarArray("m_" + i, c, 0,1);
            game[i] = makeIntVarArray("g_" + i, c, -1,8);
            /*
            for(int j = 0; j < c; j++) {

                // 0: no mine, 1: mine
                mines[i][j] = makeIntVar("m_" + i + "_" + j, 0, 1);

                // mirrors the problem matrix
                game[i][j] = makeIntVar("g_" + i + "_" + j, -1, 8);

            }
            */
        }

        /*
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                System.out.print(problem[i][j] + " ");
            }
            System.out.println();
        }
        */

        // Add the constraints
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {

                // This is a known value of neighbours
                if (problem[i][j] > X) {

                    // mirroring the problem matrix.
                    model.addConstraint(eq(game[i][j], problem[i][j]));

                    // This could not be a mine.
                    model.addConstraint(eq(mines[i][j], 0));

                    // Sum the number of neighbours: same as game[i][j].
                    // 
                    // Note: Maybe this could be modelled more elegant
                    // instead of using an ArrayList.
                    ArrayList<IntegerVariable> lst = new ArrayList<IntegerVariable>();
                    for(int a = -1; a <= 1; a++) {
                        for(int b = -1; b <= 1; b++) {
                            if (i+a >= 0 && j+b >=  0 &&
                                i+a < r && j+b < c) {
                                lst.add(mines[i+a][j+b]);
                            }
                        }                        
                    }
                    model.addConstraint(eq(sum(lst.toArray(new IntegerVariable[1])), game[i][j]));

                } // end if problem[i][j] > X

            } // end for j

        } // end for i


    } // end model


    /**
     *
     * search()
     *
     */
    public void search() {

        s = new CPSolver();
        s.read(model);

        // s.setGeometricRestart(2, 1); // don't work! "Cannot find ...."

        // variable selector
        s.setVarIntSelector(new MinDomain(s)); // the best?
        // s.setVarIntSelector(new DomOverDeg(s)); // not so bad
        //s.setVarIntSelector(new DomOverDynDeg(s)); // worse than DomOverDeg
        // s.setVarIntSelector(new MostConstrained(s)); // worse than DomOverDeg
        // s.setVarIntSelector(new RandomIntVarSelector(s)); // not good
        // s.setVarIntSelector(new MinDomain(s, s.getVar(x))); // strange results
        // s.setVarIntSelector(new LexIntVarSelector(
        //                                                new MinDomain(s),
        //                                                new DomOverDeg(s)));  // not good

        // value interator
        s.setValIntIterator(new DecreasingDomain()); // good
        // s.setValIntIterator(new IncreasingDomain()); // worse than DecreasingDomain

        // value selector
        s.setValIntSelector(new MinVal());
        // s.setValIntSelector(new MaxVal());
        // s.setValIntSelector(new MidVal());
        // s.setValIntSelector(new RandomIntValSelector()); // not bad...

        s.monitorTimeLimit(true);
        s.monitorBackTrackLimit(true);
        s.monitorNodeLimit(true);
        s.monitorFailLimit(true);

        // s.solveAll();
        s.solve();
        
        s.printRuntimeStatistics(); // sic!
        /*
        System.out.println("getBackTrackCount: " + s.getBackTrackCount());
        System.out.println("getNodeCount: " + s.getNodeCount());
        System.out.println("getFailLimit: " + s.getFailCount());
        */

        // System.out.println("getCpuTimeCount" + s.getCpuTimeCount()); // don't work

        // System.out.println(s.pretty());

        
        if (s.isFeasible()) {

            // ChocoUtils.printAllSolutions(model, s);
            int sol = 1;
            // int numVariables = s.getNbIntVars();
            do {
                System.out.println("\nSolution # " + sol);

                for(int i = 0; i < r; i++) {
                    for(int j = 0; j < c; j++) {
                        System.out.print(s.getVar(mines[i][j]).getVal() + " ");
                    }
                    System.out.println();
                }

                sol++;

            } while (s.nextSolution() == Boolean.TRUE);

        } else {

            System.out.println("No solutions.");

        } // end if result


    } // end search


    /**
     *
     * Reads a minesweeper file.
     * File format:
     *  # a comment which is ignored
     *  % a comment which also is ignored
     *  number of rows
     *  number of columns
     *  <
     *    row number of neighbours lines...
     *  >
     * 
     * 0..8 means number of neighbours, "." mean unknown (may be a mine)
     * 
     * Example (from minesweeper0.txt)
     * # Problem from Gecode/examples/minesweeper.cc  problem 0
     * 6
     * 6
     * ..2.3.
     * 2.....
     * ..24.3
     * 1.34..
     * .....3
     * .3.3..
     *
     */
    public void readFile(String file) {

        System.out.println("readFile(" + file + ")");
        int lineCount = 0;
        
        try {

            BufferedReader inr = new BufferedReader(new FileReader(file));
            String str;
            while ((str = inr.readLine()) != null && str.length() > 0) {

                str = str.trim();

                // ignore comments
                if(str.startsWith("#") || str.startsWith("%")) {
                    continue;
                }

                System.out.println(str);
                if (lineCount == 0) {
                    r = Integer.parseInt(str); // number of rows
                } else if (lineCount == 1) {
                    c = Integer.parseInt(str); // number of columns
                    problem = new int[r][c];
                } else {
                    // the problem matrix
                    String row[] = str.split("");
                    for(int j = 1; j <= c; j++) {
                        String s = row[j];
                        if (s.equals(".")) {
                            problem[lineCount-2][j-1] = -1;
                        } else {
                            problem[lineCount-2][j-1] = Integer.parseInt(s);
                        }
                    }
                }

                lineCount++;

            } // end while

            inr.close();

        } catch (IOException e) {
            System.out.println(e);
        }

    } // end readFile


    /**
     * 
     * main()
     *
     */
    public static void main(String args[]) {

        MineSweeper minesweeper = new MineSweeper();
        String file = "";
        if (args.length > 0) {
            file = args[0];
            minesweeper.readFile(file);
        }
        minesweeper.model();
        minesweeper.search();

    } // end main

} // end class