Closed heyLu closed 9 years ago
We can now solve the above two, putting the rows and columns in one list and sorting it by the number of possibilities per line once at the start.
However, we can't solve bigger problems like the following two:
nonogramGenForceLimes(
[[3],[5],[3,1],[2,1],[3,3,4],[2,2,7],[6,1,1],[4,2,2],[1,1],[3,1],[6],[2,7],[6,3,1],[1,2,2,1,1],[4,1,1,3],[4,2,2],[3,3,1],[3,3],[3],[2,1]],
[[2],[1,2],[2,3],[2,3],[3,1,1],[2,1,1],[1,1,1,2,2],[1,1,3,1,3],[2,6,4],[3,3,9,1],[5,3,2],[3,1,2,2],[2,1,7],[3,3,2],[2,4],[2,1,2],[2,2,1],[2,2],[1],[1]],
F, _),
printNonogram(F).
forcing doesn't help us much here, only giving us about 10 fields.
"genie", an example that's distributed with this nonogram solver
nonogramSolveSorted([[20, 5], [15, 3, 3], [11, 3, 5], [8, 5, 2, 2], [6, 2, 2, 5], [5, 10, 3], [4, 4, 5, 2], [3, 7, 1, 6], [2, 19, 3], [2, 21, 2, 1], [1, 6, 1, 14, 1], [1, 6, 13, 1], [1, 5, 11, 1], [4, 12], [3, 11], [7, 3, 10], [1, 3, 2, 1, 3, 9], [2, 1, 2, 1, 2, 1, 4, 3], [2, 5, 1, 3, 2, 2, 4], [3, 3, 1, 3, 1, 2, 5], [4, 3, 1, 3, 1, 1, 5], [2, 2, 3, 3, 2, 1, 1, 4], [1, 1, 3, 2, 4], [2, 2, 2, 2, 2, 1, 4], [5, 10, 3, 5], [2, 7, 9], [2, 3, 5, 11], [6, 22], [2, 3, 1, 10, 1], [3, 2, 3, 1, 5, 5, 2], [5, 2, 2, 1, 8, 6], [5, 2, 1, 1, 11, 6], [3, 2, 1, 3, 3, 9, 3], [3, 1, 1, 5, 10, 2], [3, 2, 2, 1, 16], [3, 2, 4, 3, 12, 6], [3, 2, 19, 1, 4], [5, 8, 7, 3, 2, 1], [7, 2, 3, 3, 3, 2, 1], [7, 12, 2, 1], [10, 4, 10, 2, 1], [12, 1, 2, 1, 2, 1], [1, 1, 4, 1, 13, 1], [3, 3, 4, 1, 1, 1, 2], [7, 4, 2, 1, 2, 2], [1, 2, 2, 7, 2, 1, 2], [4, 5, 3, 1, 2, 6], [11, 2, 3, 1, 8], [2, 12], [13, 9, 8, 9]], [[13, 3, 3, 1], [10, 2, 2, 1], [8, 4, 2, 2, 1], [7, 2, 5, 5, 1], [6, 13, 3, 1, 1], [5, 14, 1, 1, 1], [4, 13, 3, 1, 1], [4, 2, 5, 5, 1], [3, 4, 2, 2, 1], [3, 2, 2, 1], [3, 3, 2, 2, 3, 1], [2, 2, 8, 6, 1], [2, 1, 1, 3, 2, 2, 4, 2], [2, 1, 2, 2, 2, 2, 5, 2, 9], [2, 2, 3, 1, 1, 2, 2, 2, 1, 5], [1, 6, 6, 2, 1, 1, 1, 1, 2, 1], [1, 13, 2, 2, 1, 1, 2, 2, 2, 1], [1, 8, 1, 2, 2, 1, 2, 4, 1], [1, 6, 5, 4, 3, 1], [1, 6, 7, 1, 1, 2, 3, 1], [6, 1, 4, 2, 2, 7, 1], [5, 1, 1, 2, 1, 2, 2, 1], [5, 4, 4, 2, 1, 1], [6, 2, 4, 1, 1, 1, 1], [2, 3, 3, 4, 2, 1, 3], [8, 2, 4, 1, 2, 3], [2, 2, 4, 4, 2, 2, 7, 2], [2, 7, 4, 2, 1, 2, 3, 3, 1, 2, 2], [6, 4, 6, 1, 1, 11, 1, 4], [1, 10, 1, 4, 2, 14, 1, 2], [2, 1, 7, 1, 1, 1, 9, 2, 1, 2], [1, 9, 4, 1, 9, 2, 1, 2], [1, 9, 1, 12, 2, 1, 2], [1, 3, 9, 12, 2, 1, 1], [6, 11, 4, 8, 2, 1, 1], [2, 2, 14, 6, 6, 2, 1, 2], [5, 11, 7, 6, 2, 1, 1, 1], [3, 8, 1, 6, 2, 3, 1, 2, 1], [8, 3, 7, 2, 2, 2, 4, 1], [2, 5, 2, 8, 4, 2, 2, 2, 1], [1, 23, 2, 2, 1], [21, 10, 3, 1], [13, 4, 5, 4, 1], [7, 4, 2, 2, 1], [8, 1]], F)
even nonogramGenForce
runs out of stack space. the cols
call in commons
takes too long, e.g. length(L, 45), time((possibilities([1,1,1,1], L, PS), commons(PS, C))).
already about 10 seconds.
we could fix this by writing a combination of possibilities
and commons
, that aggregates the possibilities while generating them.
More fun at heyLu/nonogram-prolog#1!
We're still not solving certain nonograms, let's collect them here.
the famous one: most likely requires guessing
a bigger one, where many values are missing