Download
/*
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:
//
// From http://twan.home.fmf.nl/blog/haskell/Nonograms.details
// 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.
// We start with the smaller dimension.
// 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) {
aut.addTransition(i,i,0);
aut.addTransition(i,i+1,1);
} else {
if (i < num_states) {
if (tmp[i+1] == 1) {
aut.addTransition(i,i+1,1);
} else {
aut.addTransition(i,i+1,0);
}
}
}
}
aut.addTransition(num_states,num_states+1,0);
aut.addTransition(num_states+1,num_states+1,0);
return aut;
} // end make_automaton
This work is licensed under a Creative Commons Attribution 4.0 International License.