/* 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 */ import cotfd; int t0 = System.getCPUTime(); // // Problems: // // From http://twan.home.fmf.nl/blog/haskell/Nonograms.details // The lambda picture // include "nonogram_lambda"; /* 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] ]; */ // "hard" // Note: I don't remember where I found this problem, and it isn't very hard. // include "nonogram_hard"; // https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p98.pl // 'Hen' // include "nonogram_hen"; // ECLiPSe // http://eclipse.crosscoreop.com/eclipse/examples/nono.ecl.txt // Problem n3 ( http://www.pro.or.jp/~fuji/java/puzzle/nonogram/index-eng.html ) // 'Car' // include "nonogram_car"; // http://eclipse.crosscoreop.com/eclipse/examples/nono.ecl.txt // Problem n4 // include "nonogram_n4"; // http://eclipse.crosscoreop.com/eclipse/examples/nono.ecl.txt // Problem n6 // include "nonogram_n6"; // Nonogram problem from Gecode: Nonunique // There are 43 solutions to this nonogram. // http://www.gecode.org/gecode-doc-latest/classNonogram.html // // include "nonogram_nonunique"; // Nonogram problem from Gecode: Dragonfly // http://www.gecode.org/gecode-doc-latest/classNonogram.html // include "nonogram_dragonfly"; // the example quoted in Optima#65, Mathematical Programming Society Newsletter // Via ECLiPSe: nono.ecl // (This is the same as dragonfly!) // include "nonogram_optima"; // 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 include "nonogram_p200"; // Nonogram problem: P199, difficulty 8 // From ECLiPSe http://87.230.22.228/examples/nono_regular.ecl.txt // include "nonogram_p199"; // 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"; // Nonogram problem from Gecode: Bear // http://www.gecode.org/gecode-doc-latest/classNonogram.html // include "nonogram_bear"; // Nonogram problem from Gecode: Castle // From http://www.cs.kuleuven.be/~bmd/nonogram.pl // Statistics: // num_solutions: 1 // time: 780 // #choices = 27 // #fail = 33 // #propag = 241040 // comet -j2 nonogram_regular.co 1,39s user 0,10s system 97% cpu 1,524 total // include "nonogram_castle"; // Nonogram problem from Gecode: "difficult" // num_solutions: 1 // time: 1550 // #choices = 5303 // #fail = 10606 // #propag = 3884317 // comet -j2 nonogram_regular.co 2,71s user 0,08s system 97% cpu 2,859 total // include "nonogram_difficult"; // from http://www-lp.doc.ic.ac.uk/UserPages/staff/ft/alp/humour/visual/nono.html // Via ECLiPSe http://87.230.22.228/examples/nono_regular.ecl.txt // include "nonogram_ps"; // Nonogram problem from Gecode: Crocodile // http://www.gecode.org/gecode-doc-latest/classNonogram.html // include "nonogram_crocodile"; Solver m(); // // The grid // var{int} board[1..rows, 1..cols](m, 0..1); Integer num_solutions(0); // explore { exploreall { 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(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(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 m, int[] rules, var{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 aut = make_automaton(rules_tmp); m.post(regular(y, aut)); } // end check_rule // // Build the transition matrix for a nonogram pattern. // function Automaton make_automaton(int[] pattern) { int p_len = pattern.getSize(); int num_states = p_len + sum(i in 1..p_len) pattern[i]; Automaton 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