Lab Assignment

Unblock puzzle

Introduction

In this exercise we will encode in ASP a simple planning puzzle called Unblock. The puzzle consists of a set of tiles of different dimensions on a square grid of n × n cells (normally, 6 × 6). Tiles can be horizontal blocks of 1 × k cells or vertical blocks of k × 1 cells (in all cases k > 1). Each block can only be moved in its longitudinal axis, always inside the grid and without pushing the other blocks. The goal consists in moving a particular block (the goal block in red) to a given grid position (the exit position).

To understand the game rules, you can try playing at the webpages below (a smartphone version, Unblock Me Free, is also available for Android and iPhone);

http://www.quickflashgames.com/games/unblock/
http://www.zjuegos.com/juegos/unblock-it.html

Steps

We will build a program that performs the following steps:

1. Read an Unblock puzzle from a text file with the following format. The file will begin with n text lines of n characters. Each character can be a dot '.' to represent that the cell is empty, or a letter 'a' to 'z' meaning that a block with that name is on that cell. The last line contains an expression X=M meaning that the goal block is X and its target position is some integer value M=0 .. n-2. M represents a column index if the block is horizontal, or a row index if the block is vertical. As an example, the first level in the picture above would be represented as the text file:
   
   
   

   ...a.. ...a.. bb.a.. ...... c.ddd. c..ee. b=4

   
   
   Note that the goal block in this case is b and its target position is column 4. The program that reads these input files and generates the corresponding ASP facts can be written in any standard language (C, java, python, perl,...) but without using non-standard libraries (i.e. exclusively using the standard language installation).
   


2. Encode the puzzle as an ASP incremental planning problem. 
   
   
3. Call the solver clingo and obtain a solution in the form move(B,D,T) where B is a block, D an increment (1 or -1) and T a time instant. For instance move(e,-1,1) move(a,1,2) would mean that we move block e one cell to the left at instant 1, and then we move block a one cell downwards at instant 2.

Additional comments

• Most Unblock games will count a shift of N cells in the same direction as a single movement. For simplicity, we will assume that each movement exclusively implies one cell shift, that is, we can increment the column (for horizontal blocks) or the row (for vertical ones) in +1 or -1 positions.
• These are some problem instances and their solutions
• level1.txt, sol1.txt
  
• level2.txt, sol2.txt
  
• level3.txt, sol3.txt
• level4.txt, sol4.txt
  
• level5.txt, sol5.txt
  
• level6.txt, sol6.txt
• level7.txt, sol7.txt

Assessment & delivery

The maximum grade for this exercise (1a) is 1 point = 10% of the course. The deadline for delivery is Friday, April 29h, 2016 using the lab work mailbox or buzón de prácticas.