Nonogram solver: Difference between revisions
+ D entry |
More pythonic and faster Python entry |
||
Line 432: | Line 432: | ||
=={{header|Python}}== |
=={{header|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. |
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 |
def gen_row(w, s): |
||
⚫ | |||
def gen_pad(w, n): |
def gen_pad(w, n): |
||
if n: |
if n: |
||
for l in |
return [[[2] * l] + r for l in xrange(1, w - n + 1) |
||
for r in gen_pad(w-l, n-1) |
for r in gen_pad(w - l, n - 1)] |
||
return [[[2]*w]] |
return [[[2] * w]] |
||
def interlace(z, o): |
def interlace(z, o): |
||
Line 444: | Line 446: | ||
l[0::2] = z |
l[0::2] = z |
||
l[1::2] = o |
l[1::2] = o |
||
return |
return sum(l, []) |
||
⚫ | |||
⚫ | |||
for x in gen_pad(w - sum(s) + 2, len(s))] |
|||
⚫ | |||
⚫ | |||
⚫ | |||
def deduce(hr, vr): |
def deduce(hr, vr): |
||
⚫ | |||
def allowable(row): |
def allowable(row): |
||
return reduce(lambda a,b:[x|y for x,y in |
return reduce(lambda a, b: [x | y for x, y in izip(a, b)], row) |
||
def fits(a, b): |
def fits(a, b): |
||
return all( |
return all(x & y for x, y in izip(a, b)) |
||
# |
# See if any value in a given column is fixed; |
||
# mark its corresponding row for future fixup |
# if so, mark its corresponding row for future fixup. |
||
def fix_col(n): |
def fix_col(n): |
||
fixable.remove(-n - 1) |
|||
c = [x[n] for x in can_do] |
c = [x[n] for x in can_do] |
||
cols[n] = [x for x in cols[n] if fits(x,c)] |
cols[n] = [x for x in cols[n] if fits(x, c)] |
||
for i,x in enumerate(allowable(cols[n])): |
for i,x in enumerate(allowable(cols[n])): |
||
v = x & can_do[i][n] |
v = x & can_do[i][n] |
||
if v == can_do[i][n]: |
if v == can_do[i][n]: |
||
continue |
|||
fixable.add(i + 1) |
|||
can_do[i][n] = v |
can_do[i][n] = v |
||
# |
# Ditto, for rows. |
||
def fix_row(n): |
def fix_row(n): |
||
fixable.remove(n + 1) |
|||
c = can_do[n] |
c = can_do[n] |
||
rows[n] = [x for x in rows[n] if fits(x,c)] |
rows[n] = [x for x in rows[n] if fits(x, c)] |
||
for i,x in enumerate(allowable(rows[n])): |
for i, x in enumerate(allowable(rows[n])): |
||
v = x & can_do[n][i] |
v = x & can_do[n][i] |
||
if v == can_do[n][i]: |
if v == can_do[n][i]: |
||
continue |
|||
fixable.add(-i - 1) |
|||
can_do[n][i] = v |
can_do[n][i] = v |
||
def show_gram(m): |
def show_gram(m): |
||
# |
# If there's 'x', something is wrong. |
||
# |
# If there's '?', needs more work. |
||
for x in m: |
for x in m: |
||
print " ".join("x#.?"[i] for i in x) |
|||
print '-' * (2 * len(vr) - 1) |
|||
w, h = len(vr), len(hr) |
w, h = len(vr), len(hr) |
||
fixable = |
fixable = set() |
||
rows = [ |
rows = [gen_row(w, x) for x in hr] |
||
cols = [ |
cols = [gen_row(h, x) for x in vr] |
||
can_do = [allowable(x) for x in rows] |
can_do = [allowable(x) for x in rows] |
||
# initially mark all columns for update |
# initially mark all columns for update |
||
for i in |
for i in xrange(w): |
||
fixable.add(-i - 1) |
|||
while fixable: |
while fixable: |
||
i = |
i = next(iter(fixable)) |
||
if i < 0: |
if i < 0: |
||
fix_col(-i - 1) |
|||
else: |
|||
fix_row(i - 1) |
|||
show_gram(can_do) |
show_gram(can_do) |
||
# return if solution is unique |
# return if solution is unique |
||
if all( |
if all(can_do[i][j] in (1, 2) for j in xrange(w) for i in xrange(h)): |
||
return |
return |
||
out = [0] * h |
|||
print "Solution not unique, doing exhaustive search:" |
print "Solution not unique, doing exhaustive search:" |
||
def try_all(n = 0 |
def try_all(n = 0): |
||
if n >= h: |
if n >= h: |
||
for j in |
for j in xrange(w): |
||
if [x[j] for x in out] not in cols[j]: |
if [x[j] for x in out] not in cols[j]: |
||
return |
|||
show_gram(out) |
show_gram(out) |
||
return |
return |
||
Line 520: | Line 531: | ||
try_all() |
try_all() |
||
⚫ | |||
def solve(p, show_runs=True): |
|||
s = [[[ord(c)-ord('A')+1 for c in w] for w in l.split( |
s = [[[ord(c) - ord('A') + 1 for c in w] for w in l.split()] |
||
⚫ | |||
⚫ | |||
⚫ | |||
if show_runs: |
|||
⚫ | |||
⚫ | |||
deduce(s[0], s[1]) |
deduce(s[0], s[1]) |
||
print "\n" |
print "\n" |
||
# read from file file |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
# Read problems from file. |
|||
⚫ | |||
⚫ | |||
for p in (x for x in open(fn).read().split("\n\n") if x): |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
main()</lang> |
|||
⚫ | |||
⚫ | |||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 10:25, 31 March 2014
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):
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"
For this task try to solve the problems read from a "nonogram_problems.txt" file, copied from this:
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
More info:
http://en.wikipedia.org/wiki/Nonogram
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):
https://sites.google.com/site/prologsite/prolog-problems
Some Haskell solutions:
http://www.haskell.org/haskellwiki/99_questions/Solutions/98
http://twanvl.nl/blog/haskell/Nonograms
PicoLisp solution:
http://picolisp.com/5000/!wiki?99p98
Bonus Problem: generate nonograms with unique solutions, of desired height and width.
D
<lang d>import std.stdio, std.range, std.file, std.algorithm, std.array,
std.string;
/// Create all patterns of a row or col that match given runs. int[][] genRow(in int w, /*in*/ int[] s) {
static int[][][] genPad(in int w, in int n) pure nothrow { if (n) { typeof(return) result; foreach (immutable l; 1 .. w - n + 1) foreach (r; genPad(w - l, n - 1)) result ~= [[2].replicate(l)] ~ r; return result; } else return [[[2].replicate(w)]]; }
static int[] interlace(in int[][] z, in int[][] o) pure nothrow { assert(z.length == o.length + 1); typeof(return) result; foreach (immutable i; 0 .. z.length + o.length) result ~= (i % 2) ? o[i / 2] : z[i / 2]; return result; }
const ones = s.map!(i => [1].replicate(i)).array; return genPad(w - s.sum + 2, s.length) .map!(x => interlace(x, ones)[1.. $-1]).array;
}
// Fix inevitable value of cells, and propagate. void deduce(/*in*/ int[][] hr, /*in*/ int[][] vr) {
static int[] allowable(/*in*/ int[][] row) pure /*nothrow*/ { return row.reduce!((a, b) => zip(a, b) .map!(xy => xy[0] | xy[1]).array); }
static bool fits(in int[] a, in int[] b) pure /*nothrow*/ { return zip(a, b).all!(xy => xy[0] & xy[1]); }
immutable int w = vr.length; immutable int h = hr.length; bool[int] fixable; // A set. auto rows = hr.map!(x => genRow(w, x)).array; auto cols = vr.map!(x => genRow(h, x)).array; auto canDo = rows.map!allowable.array;
// See if any value a given column is fixed; if so, // mark its corresponding row for future fixup. void fixCol(in int n) /*nothrow*/ { fixable.remove(-n - 1); /*const*/ auto c = canDo.map!(x => x[n]).array; cols[n] = cols[n].filter!(x => fits(x, c)).array; foreach (immutable i, immutable x; allowable(cols[n])) { immutable v = x & canDo[i][n]; if (v == canDo[i][n]) continue; fixable[i + 1] = true; canDo[i][n] = v; } }
// Ditto, for rows. void fixRow(in int n) { fixable.remove(n + 1); /*const*/ auto c = canDo[n]; rows[n] = rows[n].filter!(x => fits(x, c)).array; foreach (immutable i, immutable x; allowable(rows[n])) { immutable v = x & canDo[n][i]; if (v == canDo[n][i]) continue; fixable[-i - 1] = true; canDo[n][i] = v; } }
void showGram(in int[][] m) { // If there's 'x', something is wrong. // If there's '?', needs more work. foreach (const x; m) writefln("%-(%c %)", x.map!(i => "x#.?"[i])); writeln("-".replicate(2 * vr.length - 1)); }
// Initially mark all columns for update. foreach (immutable i; 0 .. w) fixable[-i - 1] = true;
while (fixable.length) { immutable i = fixable.byKey.front; if (i < 0) fixCol(-i - 1); else fixRow(i - 1); }
showGram(canDo);
// Return if solution is unique. if (cartesianProduct(h.iota, w.iota) .all!(ij => canDo[ij[0]][ij[1]] == 1 || canDo[ij[0]][ij[1]] == 2)) return;
"Solution not unique, doing exhaustive search:".writeln; auto out_ = new const(int)[][](h);
void tryAll(in int n = 0) { if (n >= h) { foreach (immutable j; 0 .. w) { if (!cols[j].canFind(out_.map!(x => x[j]).array)) return; } showGram(out_); return; } foreach (const x; rows[n]) { out_[n] = x; tryAll(n + 1); } }
tryAll;
}
void solve(in string p, in bool showRuns=true) {
/*const*/ auto 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]); writeln('\n');
}
void main() {
// Read problems from file. immutable fn = "nonogram_problems.txt"; foreach (p; fn.readText.split("\n\n").filter!(p => !p.empty)) 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]] . # # # . . . . # # . # . . . . . # # # . . # # . . # # . . # # . . # # # # # # # . # # # # # . # # # # # # . . . . . . # . . . . . . # # . . . --------------- 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]] . . . . . . . . . . # # # # # # . . . . . . . . . . . . # # # . # . . # # # . . . . . # . . # # # . . . # . . . . # # # . . # # # . # # # # # # # # # # # # # # . . . # . . # . . . . . . . . . . . . # . . # . # . # # . . . . . . . . . . # # # # # # # . . # # . . . . . . . . # # . # # # # # . . . # . . . . . . . . # . . # # # # # . . # # # . # # # . # # # . . # # # # # # # # . # # # . # # # . # # # --------------------------------------- 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]] . . . . # # # . # . . . . . . . . . . . . . . . # # . # # # # . # . . . . . . . . . . . # . # # # . # # # . . . . . . . . . # # . # # # # . . . . . . . . . . . . # # # . # # # . # . . . . # # # . . . # # # . . # # . # # . . . # . # # # . . # # . . # # . # # . . . . # # . # # . . . . . . # # . # . # . . # # . # . # . . . . . . # . # # . # . . . # # # # . . . . . . . # . # . # # . . . . . # # . . . . . . . . # # . # # . . # # # # # # # # . . . . # # . # # . . . # # . . # # # # . . . . # . # # . # # . # . . . # . . # # # # . . # # # . # # # # # . . . . . # # . # . # # # . # . . . . # . . . . # # # # . . # # # . # . . . . # # # . # # # . # . # # # . # # . # # # # # # # # . . . # # # # . # # # . # # # # # # # # . . . . . # . # # # # . # # . # # # # # . . . . . # . # # # # . # # . . . # # . . . . . . . # # # # . . # # . . . # # # # # . . . # # # # # . # # # . . . # # # # # . . . # # # # . # . . . . . . . . . . # . . # # # # . # # . . . . . . . . . . . . . # # # . # # # . . . . . . . . . . . --------------------------------------- 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]] . . . . . . . . . . . . . . . . . . . . # # # # # . . # # . . . . . . . . . . . . . . # # # . . # # . # # . . . . . . . . . . . . . . # # # # # . . # # # . . . . . . . . . . . . . # # # # # # # # . . # # . . . . # # # # # . # # # # # # # # # # # . . # . # . . # # . . . . # . . . . # # # # # # . . . # . . # # . . . . . # . . . . . . . # # # . . . . # # . . . . . . . . # . . . . . . . . . . . . . # . # # . . . . . # # # # # # . . . . . . . . . # # . . # # # # # # # # # # # # # # # . . . . # # # # . . . . . # # # # # # # # # # . . # # # # # # # # . . . . # # . # . # # # # . # # # . . # # # # # # . . . . . . . . # # # # # # # # # # # # # # # # # . . . . . . . . # # # # # # # # # # # # # # # # # . . . . . . . # # # # # # # # # # # # # # # # # # . . . . . . . # . . . # # # # # # # # # # # # # # . . . . . . . # . # . # # # # # # # # # # # # # # . . . . . . . . # # # # # . . . # # # # # # # # # . . . . . . . . . . . . . . . . . # # # # # # # # . . . . . . . . . . . . . . . . . . # # # # # # # ------------------------------------------------- Extra example not solvable by deduction alone: Horizontal runs: [[2], [2], [1], [1]] Vertical runs: [[2], [2], [1], [1]] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ------- Solution not unique, doing exhaustive search: # # . . # # . . . . # . . . . # ------- # # . . # # . . . . . # . . # . ------- . # # . # # . . # . . . . . . # ------- Extra example where there is no solution: Horizontal runs: [[2], [1], [1]] Vertical runs: [[1], [1], [1]] ? # ? ? . ? ? . ? ----- Solution not unique, doing exhaustive search:
The run-time with ldc2 compiler is about 0.58 seconds. The output is the same as the Python entry.
Prolog
Works with SWI-Prolog 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_pad(w, n): if n: return [[[2] * l] + r for l in xrange(1, w - n + 1) for r in gen_pad(w - l, n - 1)] return [[[2] * w]]
def interlace(z, o): l = [0] * (len(z) + len(o)) l[0::2] = z l[1::2] = o return sum(l, [])
ones = [[1] * i for i in s] return [interlace(x, ones)[1:-1] for x in gen_pad(w - sum(s) + 2, len(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))
# See if any value in a given column is fixed; # if so, mark its corresponding row for future fixup. def fix_col(n): fixable.remove(-n - 1) 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])): v = x & can_do[i][n] if v == can_do[i][n]: continue fixable.add(i + 1) can_do[i][n] = v
# Ditto, for rows. def fix_row(n): fixable.remove(n + 1) c = can_do[n] rows[n] = [x for x in rows[n] if fits(x, c)] for i, x in enumerate(allowable(rows[n])): v = x & can_do[n][i] if v == can_do[n][i]: continue fixable.add(-i - 1) can_do[n][i] = v
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 '-' * (2 * len(vr) - 1)
w, h = len(vr), len(hr) fixable = set() rows = [gen_row(w, x) for x in hr] cols = [gen_row(h, x) for x in vr] can_do = [allowable(x) for x in rows]
# initially mark all columns for update for i in xrange(w): fixable.add(-i - 1)
while fixable: i = next(iter(fixable)) if i < 0: fix_col(-i - 1) else: fix_row(i - 1)
show_gram(can_do)
# return if solution is unique if all(can_do[i][j] in (1, 2) for j in xrange(w) for i in xrange(h)): return out = [0] * h
print "Solution not unique, doing exhaustive search:" 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 show_gram(out) return for x in rows[n]: out[n] = x try_all(n + 1)
try_all()
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.split('\n')] if show_runs: print "Horizontal runs:", s[0] print "Vertical runs:", s[1] deduce(s[0], s[1]) print "\n"
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's 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]] . # # # . . . . # # . # . . . . . # # # . . # # . . # # . . # # . . # # # # # # # . # # # # # . # # # # # # . . . . . . # . . . . . . # # . . . --------------- (...etc...)