Light-Up puzzle

This assignment consists in solving the Light-Up puzzle (try here an online game), also called Akari, and described as follows. We have a grid of n x n black or white cells. Black cells may additionally contain a number from 0 to 4. The player can place any number of light bulbs in white cells, as needed. A bulb sends horizontal and vertical rays of light: the ray lights up all adjacent white cells in the same direction until it reaches a black cell or the grid border. The rules for placing the bulbs are the following:

1. All white cells must be lighted up by some bulb
2. A light bulb cannot send a light ray on another bulb
   
3. If a black cell contains a number N, then the number of bulb cells that share an edge with the black cell must be exactly N.
   

An example of initial configuration and the corresponding solution can be seen below.

Initial configuration	Solved puzzle

Step 1. Each input instance is an ASCII file containing a squared grid (n x n) with the following format. The file contains n lines (the rows) and each line contains n characters (the columns) ended by a newline. Each cell contains a character that can be:

•  'x' = a black cell
• a digit from '0' to '4' = a black cell with the corresponding number inside
• '.' = an empty white cell that can be filled with a bulb, if needed

The following shows the input format for the initial configuration above:

x...x.x ..0.... 2....3. ....... .x....2 ....0.. 0.x...x

The file examples.zip contains several input files and their solutions.

You can also visualize the solution graphically using clingraph: you will need the files viz-lightup.lp, bulb.png and the script command show. For its use, just type, for instance:

show dom01.txt

Step 2. Write a python program he program encode.py to transform each input ASCII file into a logic program containing facts. For instance:

python3 encode.py < dom01.txt > domain.lp

will transform the example above into the set of facts:

cell(0,0,x). cell(0,4,x). cell(0,6,x). cell(1,2,0). cell(2,0,2). cell(2,5,3). cell(4,1,x). cell(4,6,2). cell(5,4,0). cell(6,0,0). cell(6,2,x). cell(6,6,x). dim(7). #const n=7.

where "cell(X,Y,V)" means that cell in row X and column Y contains value V (number 0..4 or an 'x' letter).

Step 3. Encode the light-up problem in clingo in a file called lightup.lp. You can use

clingo 0 lightup.lp domain.lp

to obtain all the answer sets. You should check that each puzzle should have a unique solution. To display the puzzle solution as an ASCII file (as those included in the examples) you can use instead the program decode.py as follows:

python3 decode.py lightup.lp domain.lp

To use this program, you need facts like cell(0,1,b) to represent, for instance, that a light bulb is placed at row 0 and column 1.

Assessment & delivery