Paint By Numbers
(Challenge added over 6 years ago.)
aka Nonograms, Crucipixel, Logic Art or a million other names.
The Problem
This challenge is based on a logic puzzle called Paint By Numbers. A Paint By Numbers puzzle consists of a rectangular grid of cells, which start empty, with a clue for each row and each column.
Clues are given as a set of numbers separated by full-stops (.) which describe how the cells are to be filled in in that row or column.
Taking the image (click for a larger version) of the unsolved puzzle to the right, the '5.5' clue for the first row indicates that there must be two blocks of 5 cells coloured in on that row, and that they are separated by at least one blank cell. Similarly, the '5.5' clue for the first column indicates the same setup for that column. However, since there are multiple ways of placing two blocks of 5 cells in both the example row and column, you must work with the other clues to deduce which cells should actually be filled.
Your program should take these clues and output the completed puzzle.
The Wikipedia page for Paint By Numbers describes various methods you can use to solve these puzzles and is therefore recommended reading.
More Information
- The clues will be given to your code on stdin, and you are expected to print the solved puzzle to stdout.
- Your code will be given the clues for each row (top to bottom), followed by a hyphen on a line of its own, then the clues for the columns (left to right). Each clue is given on a new line. The height of the solution is equal to the number of row clues and the width is equal to the number of column clues.
- Your code should output the solution using an
Xfor a filled cell and a space for an unfilled cell. Ensure you trim any trailing spaces at the end of a row if there are no more filled cells to display. - Each puzzle your code will receive has a unique solution.
- All the puzzles can be solved using simple logic by considering only one row or column at a time. Techniques 3.1 to 3.7 described on Wikipedia's Paint By Numbers page will be sufficient to solve the problems your program will be given, but you are free to use any solving method you choose.
- Your program will be run against six different puzzles for each submission you make, and your program must pass all six tests to be deemed successful.
- The puzzles will range in size between 6x6 and 15x15 inclusive.
Examples
If your program were to receive the following input :
1 1 3 - 1 1.1 2
It should print :
X X XXX
Again, note the lack of a trailing space after the X on the first output line.
As mentioned above, your program will be run six times. The same puzzles will be given for the first three runs. You can view the input and the expected output below.
For the 4th, 5th and 6th run, your program will receive a different puzzle for each run. Click here to see an example, random puzzle. Reload the page to get a new puzzle.
Thanks
Many thanks go to Mark Byers who suggested and submitted this challenge. Visit his site, he has some fun stuff on there, such as a golfed Tetris game!