/*

Nonogram (Painting by numbers)  in Comet

http://en.wikipedia.org/wiki/Nonogram
"""
Nonograms or Paint by Numbers are picture logic puzzles in which cells in a
grid have to be colored or left blank according to numbers given at the
side of the grid to reveal a hidden picture. In this puzzle type, the
numbers measure how many unbroken lines of filled-in squares there are
in any given row or column. For example, a clue of "4 8 3" would mean
there are sets of four, eight, and three filled squares, in that order,
with at least one blank square between successive groups.

"""

See problem 12 at http://www.csplib.org/.

http://www.puzzlemuseum.com/nonogram.htm

This model uses the built-in constraint regular and Automaton.
Compare this to my own home-brewn regular constraint in
http://www.hakank.org/comet/nonogram_regular.co

Many thanks to Pascal Van Hentenryck for the improvements which reduced the
running time for the P200 problem from 1:30 minutes to about 1 second. The
improvements are commented below. The significant best improvement was the
(re)ordering of 1..rows / 1..cols in the labeling.

The developments of this model has been written in the following blog posts
(sorted in reversed order of publication):

* "Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about
1 second"
http://www.hakank.org/constraint_programming_blog/2009/03/comet_nonogram_improved_solvin_1.html

* "Comet: regular constraint, a much faster Nonogram with the regular
constraint, some OPL models, and more"
http://www.hakank.org/constraint_programming_blog/2009/02/comet_regular_constraint_a_muc_1.html

* "More Comet models, e.g. Nonogram, Steiner triplets, and different set covering
problems"
http://www.hakank.org/constraint_programming_blog/2009/02/more_comet_models_eg_nonogram.html

Also, compare with the following models:
* Comet: http://www.hakank.org/comet/nonogram.co
(older model, no regular constraint)
* MiniZinc: http://www.hakank.org/minizinc/nonogram.mzn
* Gecode/R: http://www.hakank.org/gecode_r/nonogram.rb (using "regexps")

This Comet model was created by Hakan Kjellerstrand (hakank@bonetmail.com)
Also, see my Comet page: http://www.hakank.org/comet

*/

// Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

import cotfd;
int t0 = System.getCPUTime();

//
// Problems:
//

// The lambda picture
/*
int rows = 12;
int row_rule_len = 3;
int row_rules[1..rows, 1..row_rule_len] =
[
[0,0,2],
[0,1,2],
[0,1,1],
[0,0,2],
[0,0,1],
[0,0,3],
[0,0,3],
[0,2,2],
[0,2,1],
[2,2,1],
[0,2,3],
[0,2,2]
];

int cols = 10;
int col_rule_len = 2;
int col_rules[1..cols, 1..col_rule_len] =
[
[2,1],
[1,3],
[2,4],
[3,4],
[0,4],
[0,3],
[0,3],
[0,3],
[0,2],
[0,2]
];
*/

// Nonogram problem from Gecode: Dragonfly
// http://www.gecode.org/gecode-doc-latest/classNonogram.html
// include "nonogram_dragonfly";

// Nonogram problem from Gecode: P200
// http://www.gecode.org/gecode-doc-latest/classNonogram.html
// Statistics:
// Before improvements suggested by Pascal Van Hentenryck:
//  num_solutions: 1
//  time:      92726
//  #choices = 142167
//  #fail    = 284334
//  #propag  = 242312778
//  comet -j2 nonogram_regular.co  93,63s user 0,17s system 99% cpu 1:33,89 total
//
// With the improvements suggested by Pascal Van Hentenryck
// and my own implementation of regular (http://www.hakank.org/comet/nonogram_regular.co )
//   num_solutions: 1
//   time:      607
//   #choices = 520
//   #fail    = 1040
//   #propag  = 1213237
//   comet -j2 nonogram_regular.co  1,66s user 0,11s system 99% cpu 1,766 total
//
// With this model using Automaton and the built-in regular constraint.
//   num_solutions: 1
//   time:      437
//   #choices = 520
//   #fail    = 794
//   #propag  = 693993
//   comet -q nonogram_automaton.co  1,82s user 0,10s system 99% cpu 1,936 total

// data files should be imported from the "data" parent directory, for example
// include "../data/nonogram_p200";

// Nonogram problem from Wikipedia, soccer player
// http://en.wikipedia.org/wiki/Nonogram
// Also see http://en.wikipedia.org/wiki/Image:Paint_by_numbers_Animation.gif
// include "nonogram_soccer_player";

Solver<CP> m();

//
// The grid
//
var<CP>{int} board[1..rows, 1..cols](m, 0..1);

Integer num_solutions(0);
// explore<m> {
exploreall<m> {

forall(i in 1..rows) {
check_rule(m, all(j in 1..row_rule_len) row_rules[i,j], all(j in 1..cols) board[i,j]);
}

forall(j in 1..cols) {
check_rule(m, all(k in 1..col_rule_len) col_rules[j,k] , all(i in 1..rows) board[i, j]);
}

} using {

// Slightly different labelings depending on the size of the problem.
// See above for credit to Pascal Van Hentenryck.
if (rows * row_rule_len < cols * col_rule_len ) {

forall(i in 1..rows, j in 1..cols: !board[i,j].bound()) {
tryall<m>(v in 0..1) by (-v)
m.label(board[i,j], v);
onFailure m.diff(board[i,j], v);
}
} else {

forall(j in 1..cols, i in 1..rows: !board[i,j].bound()) {
tryall<m>(v in 0..1) by (-v)
m.label(board[i,j], v);
onFailure m.diff(board[i,j], v);
}
}

num_solutions++;
cout << "#fails  = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;

forall(i in 1..rows) {
forall(j in 1..cols) {
string s = " ";
if (board[i,j] == 1) {
s = "#";
}
cout << s << "";
}
cout << endl;
}
cout << endl;
cout << flush;

}

cout << "\nnum_solutions: " << num_solutions << endl;

int t1 = System.getCPUTime();
cout << "time:      " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;

//
// check_rule: The main function.
//
function void check_rule(Solver<CP> m, int[] rules, var<CP>{int}[] y) {

int r_len = sum(i in 1..rules.getSize()) (rules[i] > 0);
int rules_tmp[1..r_len];
int c = 1;
forall(i in 1..rules.getSize()) {
if (rules[i] > 0) {
rules_tmp[c] = rules[i];
c++;
}
}

Automaton<CP> aut =  make_automaton(rules_tmp);
m.post(regular(y, aut));

} // end check_rule

//
// Build the transition matrix for a nonogram pattern.
//
function Automaton<CP> make_automaton(int[] pattern) {

int p_len = pattern.getSize();
int num_states = p_len + sum(i in 1..p_len) pattern[i];

Automaton<CP> aut(1..num_states+1, 0..1, 1, {num_states, num_states+1});

// convert pattern to a 0/1 pattern for easy handling of
// the states
int tmp[1..num_states];
int c = 1;
tmp[c] = 0;
forall(i in 1..p_len) {
forall(j in 1..pattern[i]) {
tmp[++c] = 1;
}
if (c < num_states) {
tmp[++c] = 0;
}
}

// create the transition states
forall(i in 1..num_states) {
if (tmp[i] == 0) {
} else {
if (i < num_states) {
if (tmp[i+1] == 1) {
} else {
}
}
}
}