Your task is to write an algorithm that solves a nonogram. The nonograms are brain teasers, defined by a legend linked to a grid used to draw a picture. Each number in the legend sets the number of the following boxes filled with color which belongs to the given number. The following rules hold:
The program is going to read from the standard input that has the following format:
NUMBER_OF_ROWS,NUMBER_OF_COLUMNS CONSTRAINTS_FOR_ROW_1 CONSTRAINTS_FOR_ROW_2 ... CONSTRAINTS_FOR_ROW_M CONSTRAINTS_FOR_COLUMN_1 CONSTRAINTS_FOR_COLUMN_2 ... CONSTRAINTS_FOR_COLUMN_N
where each constraint has the format:
COLOR_1,NUMBER_1,COLOR_2,NUMBER_2,...,NUMBER_K
where the field “color” applies to the following number and is in a format of the character that represents the color you will use for drawing (for example '#'). The field “number” sets the size of the given block.
Input examples: csp_example.txt, input.txt, krtkek.txt, dino.txt
Output examples: csp_example.txt.out input.txt.out krtek.txt.out, dino.out.txt
Think thoroughly through the way how you formalize the task - what is going to be a variable, how are the constraints and whether the edge consistency algorithms may be applied. Start with easy depth search and improve it by using CSP techniques.
In your main class write to the comment section what formalisation you have chosen, how you represent the constraints and what CSP algorithms are implemented.
In the automatic evaluation, your program has to solve 6 different problems in the total time limit of 15 minutes.
You can get up to 14 points for your task:
It is more important to have a correct CSP implementation and integration with AC-3 rather than the fastest algorithm for solving nonograms.
Week 5 - 08/04/2018 23:59