The task of this project is to develop an ASP encoding for the Seek Numbers puzzle.
Below you can see a Seek Numbers puzzle on the left, and its solution on the right.
Given a square grid as shown on the left side, the goal is to construct a directed path by linking horizontally or vertically adjacent cells such that:
The only path satisfying these conditions for the Seek Numbers puzzle on the left is shown on the right.
To familiarize yourself with the Seek Numbers puzzle, you can try the puzzle online.
The square grid is represented by facts of the following predicates:
cell(X,Y). % the cell (X,Y) belongs to the grid
first(X,Y). % the first cell of the path (marked with a white circle) is (X,Y)
final(X,Y). % the final cell of the path (marked with a black circle) is (X,Y)
hint(X,Y,N). % the cell (X,Y) contains the hint number N
Every problem instance contains exactly one fact over first/2
and one fact over final/2
.
The example shown before is represented by the following facts:
cell(1..3,1..3).
first(1,1).
final(3,3).
hint(2,1,2).
hint(2,2,2).
The solution is represented by atoms of predicate path/4
:
path(X1,Y1,X2,Y2). % the path has an edge between the cells (X1,Y1) and (X2,Y2)
For instance, the solution of the example consists of the following atoms:
path(1,1,2,1) path(2,1,3,1) path(3,1,3,2) path(3,2,2,2)
path(2,2,1,2) path(1,2,1,3) path(1,3,2,3) path(2,3,3,3)
The directory asp
contains the files that you need for the project. In the directory asp/instances
you can find the instances (our example is ex01.lp
), and in the directory asp/solutions
you can find their solutions in json
format.
You have to submit a file named seeknumbers.lp
, included as a template in the directory asp
, that contains the following line (and no more #show
statements) so that in the output only the atoms of predicate path/4
appear:
#show path/4.
You can check if your encoding solves correctly all instances by running the Python
script test.py
as follows:
python asp/test.py -e asp/seeknumbers.lp -i asp/instances -s asp/solutions -t 180
In this case, the timeout for each instance is set to 180
seconds, but you can use any other value instead.
For help, type python asp/test.py --help
.
We recommend you to work locally in your computer, using your own installation of clingo
.
For this, you can run the next cell to generate a zip file of this directory. The zip file will be stored in the parent directory with the name seeknumbers.zip
. You can click on the folder symbol at the left of the screen to look for it and download it.
import os
from shutil import make_archive
make_archive('../seeknumbers', 'zip', os.getcwd())
You can also run your encoding in the next cell. It is not recommended to work in this notebook at Binder
, but if you do it, remember to download the files that you modify to your computer, otherwise you will lose your changes.
%%clingo 0 asp/instances/ex01.lp -
% Tips:
% - You may include the facts below to represent the differences
% between the coordinates of neighboring cells
%
% diff(0,1). diff(0,-1). diff(1,0). diff(-1,0).
% Your encoding please...
#show path/4.
You can work on the solution alone or in groups of two people. Different groups have to submit different solutions, in case of plagiarism all groups involved will fail the project.
Your solution has to correctly encode all solutions for every instance.
This is tested automatically by the script test.py
.
We will send you further instructions about the submission process from Moodle.
entirely symmetric and vary only by coordinate differences between the cells.
Please avoid code duplication due to referring to directions more specifically than needed.
It is not a good idea to distinguish directions by using atoms such as
goUp(X,Y,X,Y+1)
, goDown(X,Y,X,Y-1)
,
goRight(X,Y,X+1,Y)
, and goLeft(X,Y,X-1,Y)
.
On the other hand, it is a good idea to use atoms like
go(X,Y,X,Y+1,0,1)
, go(X,Y,X,Y-1,0,-1)
, go(X,Y,X+1,Y,1,0)
, and
go(X,Y,X-1,Y,-1,0)
because they can be treated uniformly within rules.
online to get an intuition for the problem constraints, especially regarding the bending of the path between marked cells. This may help you to identify a general strategy for testing such constraints, and then formalize it by means of appropriate auxiliary predicates and integrity constraints within an ASP encoding.
If you are stuck you can contact us. We will do out best to answer all your questions. You can send us questions and remarks either via Moodle or by email.
Start as soon as possible to avoid running out of time. However, if you still realize that you have problems making it before the deadline, please contact us instead of copying another solution.