KR: Exercise 2

Answer Set Programming

The Netwalk puzzle


The exercise must solve an scenario of the so-called Netwalk puzzle. The puzzle input is a network layout where the components have been arbitrary rotated. This is an example:


The components in the grid can be either connections (straight pipes, corners or T-joints) or computers, that act as end-points. One (and only one) connection plays the role of server (in the figure above, the gray rectangle with green leds). Depending on the scenario, the server can be on a pipe, a corner or a tjoint. The puzzle consists in finding a rotation for each component so that the whole network is connected to the server. Note that all pieces must be used and that there cannot be lose ends in pipe components. You can play Netwalk online here.

For simplicity, we will only consider the problem of finding the right orientation for each component, disregarding the number of rotations required with respect to the initial state.


Since we are not interested in the original orientation of each component, we will use an input file just describing the type of component in each grid cell using a character for each case: c - corner, l - straight line, t - joint and p - PC. When the character is a capital letter (C, L, T or P), it will point out that the server is located in that connection. As an example, the scenario above would be described as:


This text file must be translated into ASP facts that will depend on the representation you decide to use.


The output must show, for each cell, the number of clockwise turns (0, 1, 2 or 3) that are required to solve the puzzle, assuming that the 0-position is the following one in each case:

The output will use a predicate rotate(X,Y,N) that means that cell in row X, column Y, must be rotated N times. Optional: you can generate an HTML file showing the graphic output as an array of images, one per each cell.

Assessment & delivery

The maximum grade for this exercise is 1,5 points. The deadline for delivery is April 26th, 2013 May 3rd, 2013 using the lab work mailbox or buzón de prácticas.

Maintained by Pedro Cabalar. Last update April. 4th 2013