/* 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 Haskell solution: http://twan.home.fmf.nl/blog/haskell/Nonograms.details Brunetti, Sara & Daurat, Alain (2003) "An algorithm reconstructing convex lattice sets" http://geodisi.u-strasbg.fr/~daurat/papiers/tomoqconv.pdf This model uses the (global) constraint regular. 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: // 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 // // 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"; // This has a "zero clue" which wasn't handled before include "nonogram_t2"; Solver m(); // // variables // // Note: We use 1..2 as a representation of 0..1 since regular requires 0 // to be a failed state var{int} board[1..rows, 1..cols](m, 1..2); // // 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++; } } int[,] transition_fn = make_transition_matrix(rules_tmp); int n_states = transition_fn.getRange(0).getSize(); int input_max = 2; // Note: we cannot use 0 since it's the failing state int initial_state = 1; set{int} accepting_states = {n_states}; // This is the last state regular(y, n_states, input_max, transition_fn, initial_state, accepting_states); } // end check_rule 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. 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 1..2) by (-v) m.label(board[i,j],v); } } else { // This is Pascal's improvement: switching the order of the variables forall(j in 1..cols, i in 1..rows: !board[i,j].bound()) { tryall(v in 1..2) by (-v) m.label(board[i,j],v); } } num_solutions++; cout << "#propag = " << m.getNPropag() << endl; forall(i in 1..rows) { forall(j in 1..cols) { string s = " "; if (board[i,j] == 2) { 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; // // Build the transition matrix for a nonogram pattern. // function int[,] make_transition_matrix(int[] pattern) { int p_len = pattern.getSize(); int num_states = p_len + sum(i in 1..p_len) pattern[i]; // this is for handling 0-clues. It generates // just the state 1,2 if (num_states == 0) { num_states = 1; } int t_matrix[1..num_states, 1..2]; // 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 matrix t_matrix[num_states,1] = num_states; t_matrix[num_states,2] = 0; forall(i in 1..num_states) { if (tmp[i] == 0) { t_matrix[i,1] = i; t_matrix[i,2] = i+1; } else { if (i < num_states) { if (tmp[i+1] == 1) { t_matrix[i,1] = 0; t_matrix[i,2] = i+1; } else { t_matrix[i,1] = i+1; t_matrix[i,2] = 0; } } } } /* cout << "The states:" << endl; forall(i in 1..num_states) { forall(j in 1..2) { cout << t_matrix[i,j] << " "; } cout << endl; } cout << endl; */ return t_matrix; } // // This is a translation of MiniZinc's regular constraint. All comments // are from the MiniZinc code except those noted by "hakank:" // """ // The sequence of values in array 'x' (which must all be in the range 1..S) // is accepted by the DFA of 'Q' states with input 1..S and transition // function 'd' (which maps (1..Q, 1..S) -> 0..Q)) and initial state 'q0' // (which must be in 1..Q) and accepting states 'F' (which all must be in // 1..Q). We reserve state 0 to be an always failing state. // """ // function void regular(var{int}[] x, int Q, // number of states int S, // input_max int[,] d, // transition matrix int q0, // initital_state set{int} F // accepting states ) { Solver cp = x[1].getSolver(); assert(Q > 0); assert(S > 0); // d2 is the same as d, except we add one extra transition for // each possible input; each extra transition is from state zero // to state zero. This allows us to continue even if we hit a // non-accepted input. int d2[0..Q, 1..S]; forall(i in 0..Q) { forall(j in 1..S) { if (i == 0) d2[i,j] = 0; else d2[i,j] = d[i, j]; } } // If x has index set m..n, then a[m-1] holds the initial state // (q0), and a[i+1] holds the state we're in after processing // x[i]. If a[n] is in F, then we succeed (ie. accept the // string). range x_range = x.rng(); int m = min(i in x_range) i; int n = 1+max(i in x_range) i; var{int} a[m..n](cp, 0..Q); cp.inside(a[n], F); // Check the final state is in F. cp.post(a[m] == q0, onDomains); // Set a[0]. forall(i in x_range) { // cp.inside(x[i], 1..S); // Do this in case it's a var. cp.post(x[i] >= 1); // hakank: Pascal's improvement cp.post(x[i] <= S); // hakank: Pascal's improvement cp.post(a[i+1] == d2[a[i], x[i]], onDomains); // Determine a[i+1]. } }