Nonogram solver: Difference between revisions

From Rosetta Code
Content added Content deleted
m (added some line breaks in link section)
(→‎{{header|Java}}: added Java)
Line 318: Line 318:
No solution.</pre>
No solution.</pre>
The output is the same as the Python entry. The run-time with ldc2 compiler is about 0.29 seconds.
The output is the same as the Python entry. The run-time with ldc2 compiler is about 0.29 seconds.

=={{header|Java}}==
{{works with|Java|8}}
<lang java>import java.util.*;
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.toList;

public class NonogramSolver {

static String[] p1 = {"C BA CB BB F AE F A B", "AB CA AE GA E C D C"};

static String[] p2 = {"F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC", "D D AE "
+ "CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA"};

static String[] p3 = {"CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH "
+ "BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF "
+ "AAAAD BDG CEF CBDB BBB FC"};

static String[] p4 = {"E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q "
+ "R AN AAN EI H G", "E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ "
+ "ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM"};

public static void main(String[] args) {
for (String[] puzzleData : new String[][]{p1, p2, p3, p4})
newPuzzle(puzzleData);
}

static void newPuzzle(String[] data) {
String[] rowData = data[0].split("\\s");
String[] colData = data[1].split("\\s");

List<List<BitSet>> cols, rows;
rows = getCandidates(rowData, colData.length);
cols = getCandidates(colData, rowData.length);

int numChanged;
do {
numChanged = reduceMutual(cols, rows);
if (numChanged == -1) {
System.out.println("No solution");
return;
}
} while (numChanged > 0);

for (List<BitSet> row : rows) {
for (int i = 0; i < cols.size(); i++)
System.out.print(row.get(0).get(i) ? "# " : ". ");
System.out.println();
}
System.out.println();
}

// collect all possible solutions for the given clues
static List<List<BitSet>> getCandidates(String[] data, int len) {
List<List<BitSet>> result = new ArrayList<>();

for (String s : data) {
List<BitSet> lst = new LinkedList<>();

int sumChars = s.chars().map(c -> c - 64).sum();
List<String> prep = stream(s.split(""))
.map(x -> repeat(x.charAt(0) - 64, "1")).collect(toList());

for (String r : genSequence(prep, len - sumChars + 1)) {
int[] bits = r.substring(1).chars().toArray();
BitSet bitset = new BitSet(bits.length);
for (int i = 0; i < bits.length; i++)
bitset.set(i, bits[i] == 49); // ascii value of 1
lst.add(bitset);
}
result.add(lst);
}
return result;
}

// permutation generator, translated from Python via D
static List<String> genSequence(List<String> ones, int numZeros) {
if (ones.isEmpty())
return Arrays.asList(new String[]{repeat(numZeros, "0")});

List<String> result = new ArrayList<>();
for (int x = 1; x < numZeros - ones.size() + 2; x++) {
List<String> skipOne = ones.stream().skip(1).collect(toList());
for (String tail : genSequence(skipOne, numZeros - x))
result.add(repeat(x, "0") + ones.get(0) + tail);
}
return result;
}

static String repeat(int n, String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
sb.append(s);
return sb.toString();
}

/* If all the candidates for a row have a value in common for a certain cell,
then it's the only possible outcome, and all the candidates from the
corresponding column need to have that value for that cell too. The ones
that don't, are removed. The same for all columns. It goes back and forth,
until no more candidates can be removed or a list is empty (failure). */
static int reduceMutual(List<List<BitSet>> cols, List<List<BitSet>> rows) {
int countRemoved = reduce(cols, rows);
if (countRemoved != -1)
countRemoved += reduce(rows, cols);
return countRemoved;
}

static int reduce(List<List<BitSet>> a, List<List<BitSet>> b) {
int countRemoved = 0;

for (int i = 0; i < a.size(); i++) {

BitSet commonOn = new BitSet();
commonOn.set(0, b.size());
BitSet commonOff = new BitSet();

// determine which values all candidates of ai have in common
for (BitSet candidate : a.get(i)) {
commonOn.and(candidate);
candidate.stream().forEach(commonOff::set);
}

// remove from bj all candidates that don't share the forced values
for (int j = 0; j < b.size(); j++) {
final int fi = i, fj = j;

if (b.get(j).removeIf(cnd -> (commonOn.get(fj) && !cnd.get(fi))
|| (!commonOff.get(fj) && cnd.get(fi))))
countRemoved++;

if (b.get(j).isEmpty())
return -1;
}
}
return countRemoved;
}
}</lang>
<pre>. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .

. . . . . . . . . . # # # # # # . . . .
. . . . . . . . # # # . # . . # # # . .
. . . # . . # # # . . . # . . . . # # #
. . # # # . # # # # # # # # # # # # # #
. . . # . . # . . . . . . . . . . . . #
. . # . # . # # . . . . . . . . . . # #
# # # # # . . # # . . . . . . . . # # .
# # # # # . . . # . . . . . . . . # . .
# # # # # . . # # # . # # # . # # # . .
# # # # # # # # . # # # . # # # . # # #

. . . . # # # . # . . . . . . . . . . .
. . . . # # . # # # # . # . . . . . . .
. . . . # . # # # . # # # . . . . . . .
. . # # . # # # # . . . . . . . . . . .
. # # # . # # # . # . . . . # # # . . .
# # # . . # # . # # . . . # . # # # . .
# # . . # # . # # . . . . # # . # # . .
. . . . # # . # . # . . # # . # . # . .
. . . . # . # # . # . . . # # # # . . .
. . . . # . # . # # . . . . . # # . . .
. . . . . # # . # # . . # # # # # # # #
. . . . # # . # # . . . # # . . # # # #
. . . . # . # # . # # . # . . . # . . #
# # # . . # # # . # # # # # . . . . . #
# . # . # # # . # . . . . # . . . . # #
# # . . # # # . # . . . . # # # . # # #
. # . # # # . # # . # # # # # # # # . .
. # # # # . # # # . # # # # # # # # . .
. . . # . # # # # . # # . # # # # # . .
. . . # . # # # # . # # . . . # # . . .
. . . . # # # # . . # # . . . # # # # #
. . . # # # # # . # # # . . . # # # # #
. . . # # # # . # . . . . . . . . . . #
. . # # # # . # # . . . . . . . . . . .
. . # # # . # # # . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #</pre>


=={{header|Prolog}}==
=={{header|Prolog}}==

Revision as of 13:33, 10 April 2016

Nonogram solver is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A nonogram is a puzzle that provides numeric clues used to fill in a grid of cells, establishing for each cell whether it is filled or not. The puzzle solution is typically a picture of some kind.

Each row and column of a rectangular grid is annotated with the lengths of its distinct runs of occupied cells. Using only these lengths you should find one valid configuration of empty and occupied cells, or show a failure message.

Example
Problem:                 Solution:

. . . . . . . .  3       . # # # . . . .  3
. . . . . . . .  2 1     # # . # . . . .  2 1
. . . . . . . .  3 2     . # # # . . # #  3 2
. . . . . . . .  2 2     . . # # . . # #  2 2
. . . . . . . .  6       . . # # # # # #  6
. . . . . . . .  1 5     # . # # # # # .  1 5
. . . . . . . .  6       # # # # # # . .  6
. . . . . . . .  1       . . . . # . . .  1
. . . . . . . .  2       . . . # # . . .  2
1 3 1 7 5 3 4 3          1 3 1 7 5 3 4 3
2 1 5 1                  2 1 5 1

The problem above could be represented by two lists of lists: 

x = [[3], [2,1], [3,2], [2,2], [6], [1,5], [6], [1], [2]]
y = [[1,2], [3,1], [1,5], [7,1], [5], [3], [4], [3]]

A more compact representation of the same problem uses strings, where the letters represent the numbers, A=1, B=2, etc: 

x = "C BA CB BB F AE F A B"
y = "AB CA AE GA E C D C"
Task

For this task, try to solve the 4 problems below, read from a “nonogram_problems.txt” file that has this content (the blank lines are separators): 

C BA CB BB F AE F A B
AB CA AE GA E C D C

F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA

CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC

E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM
See also


This task is the problem n.98 of the "99 Prolog Problems" by Werner Hett (also thanks to Paul Singleton for the idea and the examples).

Some Haskell solutions:


PicoLisp solution:


A more restricted form of this problem is the Nonoblock task.

Bonus Problem
generate nonograms with unique solutions, of desired height and width.


D

Translation of: Python

<lang d>import std.stdio, std.range, std.file, std.algorithm, std.string;

/// Create all patterns of a row or col that match given runs. auto genRow(in int w, in int[] s) pure nothrow @safe { 

   static int[][] genSeg(in int[][] o, in int sp) pure nothrow @safe {
       if (o.empty)
           return [[2].replicate(sp)];

       typeof(return) result;
       foreach (immutable x; 1 .. sp - o.length + 2)
           foreach (const tail; genSeg(o[1 .. $], sp - x))
               result ~= [2].replicate(x) ~ o[0] ~ tail;
       return result;
   }

   const ones = s.map!(i => [1].replicate(i)).array;
   return genSeg(ones, w + 1 - s.sum).map!dropOne;

}

/// Fix inevitable value of cells, and propagate. void deduce(in int[][] hr, in int[][] vr) { 

   static int[] allowable(in int[][] row) pure nothrow @safe {
       //return row.dropOne.fold!q{ a[] |= b[] }(row[0].dup);
       return reduce!q{ a[] |= b[] }(row[0].dup, row.dropOne);
   }

   static bool fits(in int[] a, in int[] b)
   pure /*nothrow*/ @safe /*@nogc*/ {
       return zip(a, b).all!(xy => xy[0] & xy[1]);
   }

   immutable int w = vr.length,
                 h = hr.length;
   auto rows = hr.map!(x => genRow(w, x).array).array;
   auto cols = vr.map!(x => genRow(h, x).array).array;
   auto canDo = rows.map!allowable.array;

   // Initially mark all columns for update.
   bool[uint] modRows, modCols;
   modCols = true.repeat.enumerate!uint.take(w).assocArray;

   /// See if any value a given column is fixed; if so,
   /// mark its corresponding row for future fixup.
   void fixCol(in int n) /*nothrow*/ @safe {
       const c = canDo.map!(x => x[n]).array;
       cols[n] = cols[n].remove!(x => !fits(x, c)); // Throws.
       foreach (immutable i, immutable x; allowable(cols[n]))
           if (x != canDo[i][n]) {
               modRows[i] = true;
               canDo[i][n] &= x;
           }
   }

   /// Ditto, for rows.
   void fixRow(in int n) /*nothrow*/ @safe {
       const c = canDo[n];
       rows[n] = rows[n].remove!(x => !fits(x, c)); // Throws.
       foreach (immutable i, immutable x; allowable(rows[n]))
           if (x != canDo[n][i]) {
               modCols[i] = true;
               canDo[n][i] &= x;
           }
   }

   void showGram(in int[][] m) {
       // If there's 'x', something is wrong.
       // If there's '?', needs more work.
       m.each!(x => writefln("%-(%c %)", x.map!(i => "x#.?"[i])));
       writeln;
   }

   while (modCols.length > 0) {
       modCols.byKey.each!fixCol;
       modCols = null;
       modRows.byKey.each!fixRow;
       modRows = null;
   }

   if (cartesianProduct(h.iota, w.iota)
       .all!(ij => canDo[ij[0]][ij[1]] == 1 || canDo[ij[0]][ij[1]] == 2))
       "Solution would be unique".writeln;
   else
       "Solution may not be unique, doing exhaustive search:".writeln;

   // We actually do exhaustive search anyway. Unique
   // solution takes no time in this phase anyway.
   auto out_ = new const(int)[][](h);

   uint tryAll(in int n = 0) {
       if (n >= h) {
           foreach (immutable j; 0 .. w)
               if (!cols[j].canFind(out_.map!(x => x[j]).array))
                   return 0;
           showGram(out_);
           return 1;
       }
       typeof(return) sol = 0;
       foreach (const x; rows[n]) {
           out_[n] = x;
           sol += tryAll(n + 1);
       }
       return sol;
   }

   immutable n = tryAll;
   switch (n) {
       case 0:  "No solution.".writeln;     break;
       case 1:  "Unique solution.".writeln; break;
       default: writeln(n, " solutions."); break;
   }
   writeln;

}

void solve(in string p, in bool showRuns=true) { 

   immutable s = p.splitLines.map!(l => l.split.map!(w =>
                   w.map!(c => int(c - 'A' + 1)).array).array).array;
                   //w.map!(c => c - 'A' + 1))).to!(int[][][]);

   if (showRuns) {
       writeln("Horizontal runs: ", s[0]);
       writeln("Vertical runs: ", s[1]);
   }
   deduce(s[0], s[1]);

}

void main() { 

   // Read problems from file.
   immutable fn = "nonogram_problems.txt";
   fn.readText.split("\n\n").filter!(p => !p.strip.empty).each!(p => p.strip.solve);

   "Extra example not solvable by deduction alone:".writeln;
   "B B A A\nB B A A".solve;

   "Extra example where there is no solution:".writeln;
   "B A A\nA A A".solve;

}</lang>

Output:
Horizontal runs: [[3], [2, 1], [3, 2], [2, 2], [6], [1, 5], [6], [1], [2]]
Vertical runs: [[1, 2], [3, 1], [1, 5], [7, 1], [5], [3], [4], [3]]
Solution would be unique
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .

Unique solution.

Horizontal runs: [[6], [3, 1, 3], [1, 3, 1, 3], [3, 14], [1, 1, 1], [1, 1, 2, 2], [5, 2, 2], [5, 1, 1], [5, 3, 3, 3], [8, 3, 3, 3]]
Vertical runs: [[4], [4], [1, 5], [3, 4], [1, 5], [1], [4, 1], [2, 2, 2], [3, 3], [1, 1, 2], [2, 1, 1], [1, 1, 2], [4, 1], [1, 1, 2], [1, 1, 1], [2, 1, 2], [1, 1, 1], [3, 4], [2, 2, 1], [4, 1]]
Solution would be unique
. . . . . . . . . . # # # # # # . . . .
. . . . . . . . # # # . # . . # # # . .
. . . # . . # # # . . . # . . . . # # #
. . # # # . # # # # # # # # # # # # # #
. . . # . . # . . . . . . . . . . . . #
. . # . # . # # . . . . . . . . . . # #
# # # # # . . # # . . . . . . . . # # .
# # # # # . . . # . . . . . . . . # . .
# # # # # . . # # # . # # # . # # # . .
# # # # # # # # . # # # . # # # . # # #

Unique solution.

Horizontal runs: [[3, 1], [2, 4, 1], [1, 3, 3], [2, 4], [3, 3, 1, 3], [3, 2, 2, 1, 3], [2, 2, 2, 2, 2], [2, 1, 1, 2, 1, 1], [1, 2, 1, 4], [1, 1, 2, 2], [2, 2, 8], [2, 2, 2, 4], [1, 2, 2, 1, 1, 1], [3, 3, 5, 1], [1, 1, 3, 1, 1, 2], [2, 3, 1, 3, 3], [1, 3, 2, 8], [4, 3, 8], [1, 4, 2, 5], [1, 4, 2, 2], [4, 2, 5], [5, 3, 5], [4, 1, 1], [4, 2], [3, 3]]
Vertical runs: [[2, 3], [3, 1, 3], [3, 2, 1, 2], [2, 4, 4], [3, 4, 2, 4, 5], [2, 5, 2, 4, 6], [1, 4, 3, 4, 6, 1], [4, 3, 3, 6, 2], [4, 2, 3, 6, 3], [1, 2, 4, 2, 1], [2, 2, 6], [1, 1, 6], [2, 1, 4, 2], [4, 2, 6], [1, 1, 1, 1, 4], [2, 4, 7], [3, 5, 6], [3, 2, 4, 2], [2, 2, 2], [6, 3]]
Solution would be unique
. . . . # # # . # . . . . . . . . . . .
. . . . # # . # # # # . # . . . . . . .
. . . . # . # # # . # # # . . . . . . .
. . # # . # # # # . . . . . . . . . . .
. # # # . # # # . # . . . . # # # . . .
# # # . . # # . # # . . . # . # # # . .
# # . . # # . # # . . . . # # . # # . .
. . . . # # . # . # . . # # . # . # . .
. . . . # . # # . # . . . # # # # . . .
. . . . # . # . # # . . . . . # # . . .
. . . . . # # . # # . . # # # # # # # #
. . . . # # . # # . . . # # . . # # # #
. . . . # . # # . # # . # . . . # . . #
# # # . . # # # . # # # # # . . . . . #
# . # . # # # . # . . . . # . . . . # #
# # . . # # # . # . . . . # # # . # # #
. # . # # # . # # . # # # # # # # # . .
. # # # # . # # # . # # # # # # # # . .
. . . # . # # # # . # # . # # # # # . .
. . . # . # # # # . # # . . . # # . . .
. . . . # # # # . . # # . . . # # # # #
. . . # # # # # . # # # . . . # # # # #
. . . # # # # . # . . . . . . . . . . #
. . # # # # . # # . . . . . . . . . . .
. . # # # . # # # . . . . . . . . . . .

Unique solution.

Horizontal runs: [[5], [2, 3, 2], [2, 5, 1], [2, 8], [2, 5, 11], [1, 1, 2, 1, 6], [1, 2, 1, 3], [2, 1, 1], [2, 6, 2], [15, 4], [10, 8], [2, 1, 4, 3, 6], [17], [17], [18], [1, 14], [1, 1, 14], [5, 9], [8], [7]]
Vertical runs: [[5], [3, 2], [2, 1, 2], [1, 1, 1], [1, 1, 1], [1, 3], [2, 2], [1, 3, 3], [1, 3, 3, 1], [1, 7, 2], [1, 9, 1], [1, 10], [1, 10], [1, 3, 5], [1, 8], [2, 1, 6], [3, 1, 7], [4, 1, 7], [6, 1, 8], [6, 10], [7, 10], [1, 4, 11], [1, 2, 11], [2, 12], [3, 13]]
Solution would be unique
. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #

Unique solution.

Extra example not solvable by deduction alone:
Horizontal runs: [[2], [2], [1], [1]]
Vertical runs: [[2], [2], [1], [1]]
Solution may not be unique, doing exhaustive search:
# # . .
# # . .
. . # .
. . . #

# # . .
# # . .
. . . #
. . # .

. # # .
# # . .
# . . .
. . . #

3 solutions.

Extra example where there is no solution:
Horizontal runs: [[2], [1], [1]]
Vertical runs: [[1], [1], [1]]
Solution may not be unique, doing exhaustive search:
No solution.

The output is the same as the Python entry. The run-time with ldc2 compiler is about 0.29 seconds.

Java

Works with: Java version 8

<lang java>import java.util.*; import static java.util.Arrays.stream; import static java.util.stream.Collectors.toList;

public class NonogramSolver { 

   static String[] p1 = {"C BA CB BB F AE F A B", "AB CA AE GA E C D C"};

   static String[] p2 = {"F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC", "D D AE "
       + "CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA"};

   static String[] p3 = {"CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH "
       + "BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
       "BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF "
       + "AAAAD BDG CEF CBDB BBB FC"};

   static String[] p4 = {"E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q "
       + "R AN AAN EI H G", "E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ "
       + "ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM"};

   public static void main(String[] args) {
       for (String[] puzzleData : new String[][]{p1, p2, p3, p4})
           newPuzzle(puzzleData);
   }

   static void newPuzzle(String[] data) {
       String[] rowData = data[0].split("\\s");
       String[] colData = data[1].split("\\s");

       List<List<BitSet>> cols, rows;
       rows = getCandidates(rowData, colData.length);
       cols = getCandidates(colData, rowData.length);

       int numChanged;
       do {
           numChanged = reduceMutual(cols, rows);
           if (numChanged == -1) {
               System.out.println("No solution");
               return;
           }
       } while (numChanged > 0);

       for (List<BitSet> row : rows) {
           for (int i = 0; i < cols.size(); i++)
               System.out.print(row.get(0).get(i) ? "# " : ". ");
           System.out.println();
       }
       System.out.println();
   }

   // collect all possible solutions for the given clues
   static List<List<BitSet>> getCandidates(String[] data, int len) {
       List<List<BitSet>> result = new ArrayList<>();

       for (String s : data) {
           List<BitSet> lst = new LinkedList<>();

           int sumChars = s.chars().map(c -> c - 64).sum();
           List<String> prep = stream(s.split(""))
                   .map(x -> repeat(x.charAt(0) - 64, "1")).collect(toList());

           for (String r : genSequence(prep, len - sumChars + 1)) {
               int[] bits = r.substring(1).chars().toArray();
               BitSet bitset = new BitSet(bits.length);
               for (int i = 0; i < bits.length; i++)
                   bitset.set(i, bits[i] == 49); // ascii value of 1
               lst.add(bitset);
           }
           result.add(lst);
       }
       return result;
   }

   // permutation generator, translated from Python via D
   static List<String> genSequence(List<String> ones, int numZeros) {
       if (ones.isEmpty())
           return Arrays.asList(new String[]{repeat(numZeros, "0")});

       List<String> result = new ArrayList<>();
       for (int x = 1; x < numZeros - ones.size() + 2; x++) {
           List<String> skipOne = ones.stream().skip(1).collect(toList());
           for (String tail : genSequence(skipOne, numZeros - x))
               result.add(repeat(x, "0") + ones.get(0) + tail);
       }
       return result;
   }

   static String repeat(int n, String s) {
       StringBuilder sb = new StringBuilder();
       for (int i = 0; i < n; i++)
           sb.append(s);
       return sb.toString();
   }

   /* If all the candidates for a row have a value in common for a certain cell,
   then it's the only possible outcome, and all the candidates from the
   corresponding column need to have that value for that cell too. The ones
   that don't, are removed. The same for all columns. It goes back and forth,
   until no more candidates can be removed or a list is empty (failure). */
   static int reduceMutual(List<List<BitSet>> cols, List<List<BitSet>> rows) {
       int countRemoved = reduce(cols, rows);
       if (countRemoved != -1)
           countRemoved += reduce(rows, cols);
       return countRemoved;
   }

   static int reduce(List<List<BitSet>> a, List<List<BitSet>> b) {
       int countRemoved = 0;

       for (int i = 0; i < a.size(); i++) {

           BitSet commonOn = new BitSet();
           commonOn.set(0, b.size());
           BitSet commonOff = new BitSet();

           // determine which values all candidates of ai have in common
           for (BitSet candidate : a.get(i)) {
               commonOn.and(candidate);
               candidate.stream().forEach(commonOff::set);
           }

           // remove from bj all candidates that don't share the forced values
           for (int j = 0; j < b.size(); j++) {
               final int fi = i, fj = j;

               if (b.get(j).removeIf(cnd -> (commonOn.get(fj) && !cnd.get(fi))
                       || (!commonOff.get(fj) && cnd.get(fi))))
                   countRemoved++;

               if (b.get(j).isEmpty())
                   return -1;
           }
       }
       return countRemoved;
   }

}</lang> 

. # # # . . . . 
# # . # . . . . 
. # # # . . # # 
. . # # . . # # 
. . # # # # # # 
# . # # # # # . 
# # # # # # . . 
. . . . # . . . 
. . . # # . . . 

. . . . . . . . . . # # # # # # . . . . 
. . . . . . . . # # # . # . . # # # . . 
. . . # . . # # # . . . # . . . . # # # 
. . # # # . # # # # # # # # # # # # # # 
. . . # . . # . . . . . . . . . . . . # 
. . # . # . # # . . . . . . . . . . # # 
# # # # # . . # # . . . . . . . . # # . 
# # # # # . . . # . . . . . . . . # . . 
# # # # # . . # # # . # # # . # # # . . 
# # # # # # # # . # # # . # # # . # # # 

. . . . # # # . # . . . . . . . . . . . 
. . . . # # . # # # # . # . . . . . . . 
. . . . # . # # # . # # # . . . . . . . 
. . # # . # # # # . . . . . . . . . . . 
. # # # . # # # . # . . . . # # # . . . 
# # # . . # # . # # . . . # . # # # . . 
# # . . # # . # # . . . . # # . # # . . 
. . . . # # . # . # . . # # . # . # . . 
. . . . # . # # . # . . . # # # # . . . 
. . . . # . # . # # . . . . . # # . . . 
. . . . . # # . # # . . # # # # # # # # 
. . . . # # . # # . . . # # . . # # # # 
. . . . # . # # . # # . # . . . # . . # 
# # # . . # # # . # # # # # . . . . . # 
# . # . # # # . # . . . . # . . . . # # 
# # . . # # # . # . . . . # # # . # # # 
. # . # # # . # # . # # # # # # # # . . 
. # # # # . # # # . # # # # # # # # . . 
. . . # . # # # # . # # . # # # # # . . 
. . . # . # # # # . # # . . . # # . . . 
. . . . # # # # . . # # . . . # # # # # 
. . . # # # # # . # # # . . . # # # # # 
. . . # # # # . # . . . . . . . . . . # 
. . # # # # . # # . . . . . . . . . . . 
. . # # # . # # # . . . . . . . . . . . 

. . . . . . . . . . . . . . . . . . . . # # # # # 
. . # # . . . . . . . . . . . . . . # # # . . # # 
. # # . . . . . . . . . . . . . . # # # # # . . # 
# # . . . . . . . . . . . . . # # # # # # # # . . 
# # . . . . # # # # # . # # # # # # # # # # # . . 
# . # . . # # . . . . # . . . . # # # # # # . . . 
# . . # # . . . . . # . . . . . . . # # # . . . . 
# # . . . . . . . . # . . . . . . . . . . . . . # 
. # # . . . . . # # # # # # . . . . . . . . . # # 
. . # # # # # # # # # # # # # # # . . . . # # # # 
. . . . . # # # # # # # # # # . . # # # # # # # # 
. . . . # # . # . # # # # . # # # . . # # # # # # 
. . . . . . . . # # # # # # # # # # # # # # # # # 
. . . . . . . . # # # # # # # # # # # # # # # # # 
. . . . . . . # # # # # # # # # # # # # # # # # # 
. . . . . . . # . . . # # # # # # # # # # # # # # 
. . . . . . . # . # . # # # # # # # # # # # # # # 
. . . . . . . . # # # # # . . . # # # # # # # # # 
. . . . . . . . . . . . . . . . . # # # # # # # # 
. . . . . . . . . . . . . . . . . . # # # # # # #

Prolog

Works with: SWI-Prolog version version 6.5.3

module(clpfd) is written by Markus Triska
Solution written by Lars Buitinck

Module solve-nonogram.pl <lang Prolog>/*

  • Nonogram/paint-by-numbers solver in SWI-Prolog. Uses CLP(FD),
  • in particular the automaton/3 (finite-state/RE) constraint.
  • Copyright (c) 2011 Lars Buitinck.
  • Do with this code as you like, but don't remove the copyright notice.
  • /
- use_module(library(clpfd)).

nono(RowSpec, ColSpec, Grid) :- rows(RowSpec, Grid), transpose(Grid, GridT), rows(ColSpec, GridT).

rows([], []). rows([C|Cs], [R|Rs]) :- row(C, R), rows(Cs, Rs).

row(Ks, Row) :- sum(Ks, #=, Ones), sum(Row, #=, Ones), arcs(Ks, Arcs, start, Final), append(Row, [0], RowZ), automaton(RowZ, [source(start), sink(Final)], [arc(start,0,start) | Arcs]).

% Make list of transition arcs for finite-state constraint. arcs([], [], Final, Final). arcs([K|Ks], Arcs, CurState, Final) :- gensym(state, NextState), ( K == 0 -> Arcs = [arc(CurState,0,CurState), arc(CurState,0,NextState) | Rest], arcs(Ks, Rest, NextState, Final) ; Arcs = [arc(CurState,1,NextState) | Rest], K1 #= K-1, arcs([K1|Ks], Rest, NextState, Final)).


make_grid(Grid, X, Y, Vars) :- length(Grid,X), make_rows(Grid, Y, Vars).

make_rows([], _, []). make_rows([R|Rs], Len, Vars) :- length(R, Len), make_rows(Rs, Len, Vars0), append(R, Vars0, Vars).

print([]). print([R|Rs]) :- print_row(R), print(Rs).

print_row([]) :- nl. print_row([X|R]) :- ( X == 0 -> write(' ') ; write('x')), print_row(R).

nonogram(Rows, Cols) :- length(Rows, X), length(Cols, Y), make_grid(Grid, X, Y, Vars), nono(Rows, Cols, Grid), label(Vars), print(Grid).</lang> File nonogram.pl, used to read data in a file. <lang Prolog>nonogram :- open('C:/Users/Utilisateur/Documents/Prolog/Rosetta/nonogram/nonogram.txt', read, In, []), repeat, read_line_to_codes(In, Line_1), read_line_to_codes(In, Line_2), compute_values(Line_1, [], [], Lines), compute_values(Line_2, [], [], Columns), nonogram(Lines, Columns) , nl, nl, read_line_to_codes(In, end_of_file), close(In).

compute_values([], Current, Tmp, R) :- reverse(Current, R_Current), reverse([R_Current | Tmp], R).

compute_values([32 | T], Current, Tmp, R) :- !, reverse(Current, R_Current), compute_values(T, [], [R_Current | Tmp], R).

compute_values([X | T], Current, Tmp, R) :- V is X - 64, compute_values(T, [V | Current], Tmp, R).</lang>

Python

First fill cells by deduction, then search through all combinations. It could take up a huge amount of storage, depending on the board size. <lang python>from itertools import izip

def gen_row(w, s): 

   """Create all patterns of a row or col that match given runs."""
   def gen_seg(o, sp):
       if not o:
           return [[2] * sp]
       return [[2] * x + o[0] + tail
               for x in xrange(1, sp - len(o) + 2)
               for tail in gen_seg(o[1:], sp - x)]

   return [x[1:] for x in gen_seg([[1] * i for i in s], w + 1 - sum(s))]


def deduce(hr, vr): 

   """Fix inevitable value of cells, and propagate."""
   def allowable(row):
       return reduce(lambda a, b: [x | y for x, y in izip(a, b)], row)

   def fits(a, b):
       return all(x & y for x, y in izip(a, b))

   def fix_col(n):
       """See if any value in a given column is fixed;
       if so, mark its corresponding row for future fixup."""
       c = [x[n] for x in can_do]
       cols[n] = [x for x in cols[n] if fits(x, c)]
       for i, x in enumerate(allowable(cols[n])):
           if x != can_do[i][n]:
               mod_rows.add(i)
               can_do[i][n] &= x

   def fix_row(n):
       """Ditto, for rows."""
       c = can_do[n]
       rows[n] = [x for x in rows[n] if fits(x, c)]
       for i, x in enumerate(allowable(rows[n])):
           if x != can_do[n][i]:
               mod_cols.add(i)
               can_do[n][i] &= x

   def show_gram(m):
       # If there's 'x', something is wrong.
       # If there's '?', needs more work.
       for x in m:
           print " ".join("x#.?"[i] for i in x)
       print

   w, h = len(vr), len(hr)
   rows = [gen_row(w, x) for x in hr]
   cols = [gen_row(h, x) for x in vr]
   can_do = map(allowable, rows)

   # Initially mark all columns for update.
   mod_rows, mod_cols = set(), set(xrange(w))

   while mod_cols:
       for i in mod_cols:
           fix_col(i)
       mod_cols = set()
       for i in mod_rows:
           fix_row(i)
       mod_rows = set()

   if all(can_do[i][j] in (1, 2) for j in xrange(w) for i in xrange(h)):
       print "Solution would be unique" # but could be incorrect!
   else:
       print "Solution may not be unique, doing exhaustive search:"

   # We actually do exhaustive search anyway. Unique solution takes
   # no time in this phase anyway, but just in case there's no
   # solution (could happen?).
   out = [0] * h

   def try_all(n = 0):
       if n >= h:
           for j in xrange(w):
               if [x[j] for x in out] not in cols[j]:
                   return 0
           show_gram(out)
           return 1
       sol = 0
       for x in rows[n]:
           out[n] = x
           sol += try_all(n + 1)
       return sol

   n = try_all()
   if not n:
       print "No solution."
   elif n == 1:
       print "Unique solution."
   else:
       print n, "solutions."
   print


def solve(p, show_runs=True): 

   s = [[[ord(c) - ord('A') + 1 for c in w] for w in l.split()]
        for l in p.splitlines()]
   if show_runs:
       print "Horizontal runs:", s[0]
       print "Vertical runs:", s[1]
   deduce(s[0], s[1])


def main(): 

   # Read problems from file.
   fn = "nonogram_problems.txt"
   for p in (x for x in open(fn).read().split("\n\n") if x):
       solve(p)

   print "Extra example not solvable by deduction alone:"
   solve("B B A A\nB B A A")

   print "Extra example where there is no solution:"
   solve("B A A\nA A A")

main()</lang>

Output:
Horizontal runs: [[3], [2, 1], [3, 2], [2, 2], [6], [1, 5], [6], [1], [2]]
Vertical runs: [[1, 2], [3, 1], [1, 5], [7, 1], [5], [3], [4], [3]]
Solution would be unique
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .

Unique solution

(... etc. ...)

Racket

[See Example:Nonogram solver/Racket for editing of this section]

Template:Example:Nonogram solver/Racket

Retrieved from "https://rosettacode.org/wiki/Nonogram_solver?oldid=236598"