KR: Exercise 1
Shingoki puzzle
Introduction
In this exercise we will play with clingo
to find solutions to the Shingoki puzzle. Shingoki is
a puzzle that consists in drawing segments among points in
a grid of N x N so that all segments form a single,
cyclic path. Some grid points contain numbers in a
circle that can be additionally black or white. The puzzle
constraints are the following:
- All edges must form a single, linear loop. No crossing
or branching is allowed.
- The loop must pass through all numbered circles.
- White circles must be passed through in a straight
line.
- Black circles must always be in the corner of a turn.
- The number in each circle must be the sum of the
lengths of the 2 straight lines segments going out of
that circle.
To understand the game rules, you can try to play online
at https://www.puzzle-shingoki.com/
Steps
- Encode the Shingoki problem as an ASP program that
solves the puzzle for any instance. This program is our
Knowledge Base and will be called shingokiKB.lp
-
Each puzzle instance will be
provided as an ASCII file shingokiX.txt with the
following format. Each line contains n integer
numbers separated by (one or more) blank spaces. A
zero represents a regular grid point without any
restriction, a strictly positive number represents a
white circle and a strictly negative number represents
a black circle. As an example, the input file for the
scenario in the picture above could look like:
0 0 0
0 0 4 0 0
0 0 -2 0 -2 0
0 0
4 0 0 0 0
2 0 -6
0 -3 0 -4 0 0 -3
5
0 2 0 2 0
-2 0 0
0 0 -3 0 0
0 0 0
-2 0 -2 0 -3 0 0
0
0 0 0 0 0
0 -2 0
|
You will build a python program called encode.py
that takes the shingokiX.txt file as an input and
creates an shingokiX.lp file describing the
instance as a set of ASP facts. The file shingoki.lp will
exclusively consist of facts (it cannot contain
rules or constraints). An example of use could be:
python3
encode.py < shingoki1.txt > shingoki1.lp
- Finally, we will translate back the answer set into a
complete Shingoki solution, printing the final result in
standard output. The solution will have the following
format: show a '+' in each empty grid point, and lines
displaying the connections.
+--+ +
+--+--+--+--+
| |
|
|
+ +--+ + +--+ +--+
| | |
| | |
+ +--+ +--+ + +--+
|
|
| |
+ +--+--+ + +--+ +
|
|
| |
+--+--+ + +--+ + +
| |
| | | |
+--+--+ +--+ +--+ +
|
|
+--+ +--+ +--+--+ +
| | |
| | |
+ +--+ +--+ + +--+
|
Again, we will build a python program called decode.py
that will take the output of clingo and generate
the solution file. A possible execution could be:
clingo shingokiKB.lp shingoki1.lp | python decode.py
> solution1.txt
- You can use or adapt the following visualizer in
clingraph, viz.lp,
to be executed with the following command. The
input for the visualizer is based on predicates:
- size(N) = the number N of rows and columns in the
square grid
- number( (X,Y), N) = it means there is a non-zero
number N in the position (X,Y) in the input file
- seg((X,Y), (X',Y')) = it means that your solution
has a segment from (X,Y) to (X',Y')
Additional comments
- For simplicity, we can assume that the number of rows
and columns coincide (square grids of n x n, where n
>=0)
- Note that there are large instances where numbers may
have 2 digits
- These are some problem instances and their solutions:
shingoki-examples.zip (to be uploaded)
The maximum grade for this exercise is 2
points = 20% of the course. Delivery: use the MOODLE
assignment. Exercises can be made by groups of 2 students
at most. If so, only one student is required to deliver
the files in moodle, but all source files must contain the
names of the two group members.
Delivery: upload all files in a .zip including a
README.txt describing how to compile the code.
|