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 the file 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.
You can get up to 14 points for your task - you will get all points if you find all solutions of the problem using CSP techniques in combination with search and using the arc consistency algorithm (AC-3).
It is more important to have a correct CSP implementation and integration with AC-3 rather than the fastest algorithm for solving nonograms.
10.4.2015 3:59