The program generates every possible layout by taking the repeated Cartesian product of with a length equal to size^2. It starts taking a very long time for larger puzzles, but will solve any arbritrary size given sufficient time. This is a brute force, so is roughly O(2^n^2). Pyth, 91 72 71 bytes program that takes input of a list of the form, ] 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. Predicate 5: True for blocks of 1s, false otherwise e. :la The list of lengths of the blocks results in the indicator (given as output) Predicate 4: Check that blocks of 1s match the indicator Split the list in blocks of the same value if the indicator is then the list must have sum 4) :+a Sum the elements of the list and sum the indicator Predicate 3: The sum of 1s in a list must be equal to the sum of indicators (e.g. 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. ![]() 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. If your solution is able to solve this, you will get kudos :) The first part was basically a massive 25x25 Nonogram. I actually learnt about Nonograms from a cryptographic Christmas card released by the British Intelligence here. 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 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. You can use this online nonogram puzzle maker to test your solutions. You may assume a puzzle in always a square NxN nonogram. To allow for flexibility amongst different languages, solutions that take less than 5 mins for a 25x25 nonogram are good enough. As a benchmark, my solution works for up to roughly 25x25 within 5-10 seconds. 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). One caveat is you can't use an online solver :) ![]() 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. 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. So the solution to the above Nonogram would be: 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. 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. Above each column are listed the lengths of the runs of black squares in that column. Beside each row of the grid are listed the lengths of the runs of black squares on that row. You have a grid of squares, which must be either filled in black or left blank. The aim of this challenge is to write the shortest code that will solve a Nonogram. It is time to embark on a perilous quest to defeat the British Intelligence.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |