Can you beat the British Intelligence? (Nonogram Solver)
Haskell, 242 230 201 199 177 163 160 149 131 bytes
import Data.Lists
m=map
a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b]
g=m$list[0]id.m sum.wordsBy(<1)
Finally under 200 bytes, credit to @Bergi. Huge thanks to @nimi for helping almost halving the size.
Wow. Almost at half size now, partly because of me but mainly because of @nimi.
The magic function is (#). It finds all solutions of a given nonogram.
This is able to solve all cases, but may be super slow, since it's complexity is about O(2^(len a * len b)). A quick benchmark revealed 86GB allocated for a 5x5 nonogram.
Fun fact: It works for all nonograms, not only square ones.
How it works:
a#b: Given lists of lists of integers which represent the number of squares, generate all grids (map(chunk$length b).mapM id$a>>b>>[[0,1]]) and filter the results to keep only the valid ones.g: Given a potential nonogram it sums the runs of 1's horizontally.
Brachylog, 70 69 bytes
[R:C]hlL~l:L:1f=.:3aR,.z:3aC,
tL,?he##ElL,E:2a
.<2,_1<
@b:4f:la
e.h1,
This takes a list of two lists (first the rows indicators, then the column ones). Each indicator is itself a list (for situtions like [3,1] on one row).
This version takes about 3 minutes to solve the 5 by 5 example of the challenge.
Way more efficient version, 91 bytes
[R:C]hlL~l:L:1f:Cz:3az:Rz:3a=.:4aR,.z:4aC,
tL,?he##ElL,E:2a
.<2,_1<
:+a#=,?h
@b:5f:la
e.h1,
Try it online!
This one is not complete brute force: the only difference is that this one imposes constraints on the values of cells such that the number of 1s in each row and column matches the numbers given as indicators in the input. The only brute force part is then in finding the one grid with those constraints for which the "blocks" of 1s match what is given as indication.
This one takes about 0.05 seconds on the 5 by 5 example of the challenge. This is still way too slow for the bonus case, as I have no idea how to express the blocks of ones separated by one or more zeroes in terms of constraints.
Explanation
I will explain below the 93 bytes version. The only difference between the two is the call to predicate 3 which doesn't exist in the 70 bytes version, and the numbering of the predicates (since there is one less).
Main predicate:
[R:C] Input = [R, C] hlL The length of R is L ~l Create a list of length L :L:1f Each element of that list is a sublist of length L with cells 0 or 1 (Pred 1) %%% Part unique to the 93 bytes version :Cz Zip the rows of the list of lists with C :3a The sum of 1s in each row is equal to the sum of the indicators (Pred 3) z Transpose :Rz Zip the columns of the list of lists with R :3a The sum of 1s in each column is equal to the sum of the indicators (Pred 3) %%% =. Assign values to the cells of the list of lists which satisfy the constraints :4aR, The blocks of 1s must match the indicators on rows .z Transpose :4aC, The blocks of 1s must match the indicators on columnsPredicate 1: Forces the rows to have a specific length, and that each cell is 0 or 1.
tL, L is the length given as second element of the input ?he Take an element from the list ##ElL, That element E is itself a list of length L E:2a The elements of E are 0s and 1s (Pred 2)Predicate 2: Constrain a variable to be either 0 or 1
.<2, Input = Output < 2 _1< Output > -1Predicate 3: The sum of 1s in a list must be equal to the sum of indicators (e.g. if the indicator is [3:1] then the list must have sum 4)
:+a Sum the elements of the list and sum the indicator #=, Both sums must be equal ?h Output is the listPredicate 4: Check that blocks of 1s match the indicator
@b Split the list in blocks of the same value :5f Find all blocks of 1s (Pred 5) :la The list of lengths of the blocks results in the indicator (given as output)Predicate 5: True for blocks of 1s, false otherwise
e. Output is an element of the input h1, Its first value is 1
Pyth, 91 72 71 bytes
D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb
A program that takes input of a list of the form [size, [horizontal clues], [vertical clues]] where each clue is a list of integers (empty clues are the empty list, []), and prints every solution, newline separated, in the form of a binary grid where 1 is shaded and 0 is unshaded.
This is a brute force, so is roughly O(2^n^2). It starts taking a very long time for larger puzzles, but will solve any arbritrary size given sufficient time.
Try it online
How it works
The program generates every possible layout by taking the repeated Cartesian product of [0, 1] with a length equal to size^2. This is then split into chunks, giving a list for each horizontal line. Each line is run-length encoded, filtered by the presence of 1 and flattened, leaving the clue for that line. This is then checked against the input. The above process is repeated for the transpose of the chunks, checking the vertical lines. If there is a hit, each chunk is concatenated, and the concatenated chunks are joined on newlines and implicitly printed, with a trailing newline.
D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb Program. Input: Q
hQ Q[0], size
^ 2 Square
,01 [0, 1]
^ Cartesian product
V ) For N in the Cartesian product:
cNhQ Split N into Q[0] chunks
=T Assign that to T
=Y1 Y=1
VhQ For H in range [0, Q[0]-1]:
D:GHd def :(G, H, d)
rH8 Run-length-encode(H)
f.)T Filter by presence of 1 in character part
.nC Transpose and flatten, giving the clue
@@QdG Q[d][G], the relevant input clue
Rq Return clue==input clue
:H@TH1 :(H, T, 1)
:H@CTH2 :(H, transpose(T), 2)
=*Y* Y=Y*product of above two
IY If Y:
mjkdT Conacatenate each element of T
jb Join on newlines
b Add a newline and implicitly print
Thanks to @Pietu1998 for some tips