20
2
It is time to embark on a perilous quest to defeat the British Intelligence. The aim of this challenge is to write the shortest code that will solve a Nonogram.
What is a Nonogram?
The rules are simple. You have a grid of squares, which must be either filled in black or left blank. Beside each row of the grid are listed the lengths of the runs of black squares on that row. Above each column are listed the lengths of the runs of black squares in that column. Your aim is to find all black squares. In this puzzle type, the numbers are a form of discrete tomography that measures 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. [1][2]
So the solution to the above Nonogram would be:
Implementation Details
You can chose to represent the Nonogram however you would like and take it as an input in whatever way you deem fit for your language. Same goes for output. The aim of this challenge is to literally just get the job done; if you can solve the nonogram with whatever output your program gives, that is valid. One caveat is you can't use an online solver :)
This problem is very algorithmically challenging (np-complete) in that there is no completely efficient solution to it and as such, you won't be penalized for not being able to solve larger ones, although your answer will be heavily rewarded if it is able to handle big cases (see bonus). As a benchmark, my solution works for up to roughly 25x25 within 5-10 seconds. To allow for flexibility amongst different languages, solutions that take less than 5 mins for a 25x25 nonogram are good enough.
You may assume a puzzle in always a square NxN nonogram.
You can use this online nonogram puzzle maker to test your solutions.
Scoring
You are, of course, free to use any language you want and since this is code golf, the entries will be sorted in the order: accuracy -> length of code -> speed.
However, don't be discouraged by code golfing languages, answers in all languages that show attempts at golfing in an interesting way will be upvoted!
Bonus
I actually learnt about Nonograms from a cryptographic Christmas card released by the British Intelligence here. The first part was basically a massive 25x25 Nonogram. If your solution is able to solve this, you will get kudos :)
To make your life easier in terms of data entry, I have provided how I represented the data for this specific puzzle for your free use. The first 25 lines are the row clues, followed by a '-' separator line, followed by 25 lines of the col clues, followed by a '#' separator line, and then a representation of the grid with the square clues filled in.
7 3 1 1 7
1 1 2 2 1 1
1 3 1 3 1 1 3 1
1 3 1 1 6 1 3 1
1 3 1 5 2 1 3 1
1 1 2 1 1
7 1 1 1 1 1 7
3 3
1 2 3 1 1 3 1 1 2
1 1 3 2 1 1
4 1 4 2 1 2
1 1 1 1 1 4 1 3
2 1 1 1 2 5
3 2 2 6 3 1
1 9 1 1 2 1
2 1 2 2 3 1
3 1 1 1 1 5 1
1 2 2 5
7 1 2 1 1 1 3
1 1 2 1 2 2 1
1 3 1 4 5 1
1 3 1 3 10 2
1 3 1 1 6 6
1 1 2 1 1 2
7 2 1 2 5
-
7 2 1 1 7
1 1 2 2 1 1
1 3 1 3 1 3 1 3 1
1 3 1 1 5 1 3 1
1 3 1 1 4 1 3 1
1 1 1 2 1 1
7 1 1 1 1 1 7
1 1 3
2 1 2 1 8 2 1
2 2 1 2 1 1 1 2
1 7 3 2 1
1 2 3 1 1 1 1 1
4 1 1 2 6
3 3 1 1 1 3 1
1 2 5 2 2
2 2 1 1 1 1 1 2 1
1 3 3 2 1 8 1
6 2 1
7 1 4 1 1 3
1 1 1 1 4
1 3 1 3 7 1
1 3 1 1 1 2 1 1 4
1 3 1 4 3 3
1 1 2 2 2 6 1
7 1 3 2 1 1
#
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
And here is a slightly different version for your convenience; a comma separated tuple (row, col) where each element is list of lists.
([[7, 3, 1, 1, 7],
[1, 1, 2, 2, 1, 1],
[1, 3, 1, 3, 1, 1, 3, 1],
[1, 3, 1, 1, 6, 1, 3, 1],
[1, 3, 1, 5, 2, 1, 3, 1],
[1, 1, 2, 1, 1],
[7, 1, 1, 1, 1, 1, 7],
[3, 3],
[1, 2, 3, 1, 1, 3, 1, 1, 2],
[1, 1, 3, 2, 1, 1],
[4, 1, 4, 2, 1, 2],
[1, 1, 1, 1, 1, 4, 1, 3],
[2, 1, 1, 1, 2, 5],
[3, 2, 2, 6, 3, 1],
[1, 9, 1, 1, 2, 1],
[2, 1, 2, 2, 3, 1],
[3, 1, 1, 1, 1, 5, 1],
[1, 2, 2, 5],
[7, 1, 2, 1, 1, 1, 3],
[1, 1, 2, 1, 2, 2, 1],
[1, 3, 1, 4, 5, 1],
[1, 3, 1, 3, 10, 2],
[1, 3, 1, 1, 6, 6],
[1, 1, 2, 1, 1, 2],
[7, 2, 1, 2, 5]],
[[7, 2, 1, 1, 7],
[1, 1, 2, 2, 1, 1],
[1, 3, 1, 3, 1, 3, 1, 3, 1],
[1, 3, 1, 1, 5, 1, 3, 1],
[1, 3, 1, 1, 4, 1, 3, 1],
[1, 1, 1, 2, 1, 1],
[7, 1, 1, 1, 1, 1, 7],
[1, 1, 3],
[2, 1, 2, 1, 8, 2, 1],
[2, 2, 1, 2, 1, 1, 1, 2],
[1, 7, 3, 2, 1],
[1, 2, 3, 1, 1, 1, 1, 1],
[4, 1, 1, 2, 6],
[3, 3, 1, 1, 1, 3, 1],
[1, 2, 5, 2, 2],
[2, 2, 1, 1, 1, 1, 1, 2, 1],
[1, 3, 3, 2, 1, 8, 1],
[6, 2, 1],
[7, 1, 4, 1, 1, 3],
[1, 1, 1, 1, 4],
[1, 3, 1, 3, 7, 1],
[1, 3, 1, 1, 1, 2, 1, 1, 4],
[1, 3, 1, 4, 3, 3],
[1, 1, 2, 2, 2, 6, 1],
[7, 1, 3, 2, 1, 1]])
Sadly my website is down but it used to have a reasonably fast Nonogram solver; 5-10 minutes sounds excessive. – Neil – 2016-08-30T15:33:20.310
Related – AdmBorkBork – 2016-08-30T15:34:16.313
@Neil Grand! What language did you write it in? I was generous with the time because I didn't want to restrict users of certain slower languages. My solver works in under 10 seconds last I checked. – gowrath – 2016-08-30T15:35:16.717
The way you worded it confused me into thinking your solver takes 10 minutes. Anyway, my solver was written in Java, but it probably wasn't as fast as 10 seconds (then again it would update the screen to show its thinking, which probably slowed it down). – Neil – 2016-08-30T15:45:52.603
Can we safely assume that the grid is always a NxN square? And BTW, thanks for putting the right name on a puzzle I've seen my wife playing with some times ago. :-) (Color Cross on Facebook) – Arnauld – 2016-08-30T15:57:02.877
@Arnauld Yes you can assume it is an NxN square :) – gowrath – 2016-08-30T15:58:19.977
Can we assume that there is only one solution? – Damien – 2016-08-30T16:55:13.670
@Damien If there is more than one solution, your code should find any one of them. Is there a specific advantage to being able to assume there is only one solution? – gowrath – 2016-08-30T16:56:49.813
I'm not sure yet. But I find it easier when the solution is unique – Damien – 2016-08-30T17:13:23.597
@Damien Go for it then :) – gowrath – 2016-08-30T17:23:19.283
Is it a "nonogram" or "monogram?" You use monogram twice in the impl details section... – Socratic Phoenix – 2016-08-30T18:38:11.680
@SocraticPhoenix It's nonogram; damned autocorrect. Will fix it now. – gowrath – 2016-08-30T18:47:57.460
1http://codegolf.stackexchange.com/q/30081/21348 Related – edc65 – 2016-08-30T20:59:28.510
Are there going to be empty rows? – ThreeFx – 2016-08-31T00:07:14.447
@mbomb007 Read the bonus section. The British intelligence released a Nonogram as part 1 of a series of cryptographic challenges last christmas (possibly for employment purposes). As far as I know, no one actually managed to finish all of the challenges. – gowrath – 2016-09-02T14:06:21.410
2 question: do we need to be able to handle unsolvable onces? /// Can I create a random answer, check if it work, if not repeat? (eg bogsort?) ^^ – dwana – 2016-09-02T14:09:24.873
@dwana Your solution probably has to be deterministic. – mbomb007 – 2016-09-02T14:12:49.863
1@dwana You don't need to worry about unsolvable cases. As for the random answer, on a 25x25 nonogram, you have 2^625 possible configurations. In context, that's more than twice the number of atoms in the known universe (i.e. if you used each atom in the universe as a bit, you still wouldn't have enough space to store the possibilities). In terms of time, if it took you a nano second (generous) to check the validity of each configuration, it would take 7 lifetimes of the universe for the code to finish running :) – gowrath – 2016-09-02T14:13:10.263
1Ty for clarifying unsolvables cases. (+ i have a magical PC the validates an answer in ~ 2.1546362E-186 seconds) – dwana – 2016-09-02T14:30:30.087
@dwana Unfortunately for you, it will still take ~4.5E124 years to complete. – mbomb007 – 2016-09-02T15:30:20.433
Is there a bug in my code or does the Christmas Puzzle have no solution? My backtrace cannot even solve the first 8 rows (returns "no solution" after about half a million iterations). – Titus – 2016-09-02T17:48:59.483
@Titus It definitely has a solution, although my data entry may have been shoddy. You can check against the original link in the bonus section of the question to validate the data. – gowrath – 2016-09-02T17:52:13.883
No, the port is correct. Must be a bug somewhere. Need a smaller puzzle to test; the tiny one is always correct. – Titus – 2016-09-02T18:01:23.667
@Titus Try the 10x10s generated by the website linked in the text – gowrath – 2016-09-02T18:03:07.203
I´m done. Can I get a
/10
bonus for not using a golfing language? ;-) – Titus – 2016-09-03T19:10:03.2301Your CSV has no square hints. Here´s some JS to generate them:
s=[].fill([].fill(0,0,25),0,25);s[3][3]=s[3][4]=s3[3][12]=s3[3][13]=s3[3][21]=s[8][6]=s[8][7]=s[8][10]=s[8][14]=s[8][15]=s[8][18]=s[16][6]=s[16][11]=s[16][16]=s[16][20]=s[21][3]=s[21][4]=s[21][9]=s[21][10]=s[21][15]=s[21][20]=s[21][21]=1;
– Titus – 2016-09-03T19:10:12.800@gowrath Your tuple of lists which you say is
(row, col)
is actually(col, row)
. You should swap it around if you want it to match your other data format. – mbomb007 – 2016-09-08T14:32:05.450Additional Potential Point of Interest: The smallest unsolvable case is
[1,1],[1,1]
– HyperNeutrino – 2017-03-28T13:39:49.750