KR: Exercise 1
Masyu puzzle
|
|
|
Initial configuration
|
|
Solution
|
Introduction
In this exercise we will play with clingo to
find solutions to the Masyu puzzle. Masyu 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 can be marked with a
black or a white circle. 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 circles.
- Each white circle must be passed through in a
straight line, but there must be some turn in its
previous or in its next point (or in both)
- Each black circle must always be in the corner of a
turn, but its previous and its next points cannot
contain turns.
To understand the game rules, you can try to
play online at https://es.puzzle-masyu.com/
Steps
-
Encode the Masyu problem as an ASP
program that solves the puzzle for any instance. This
program is our Knowledge Base and will be called masyuKB.lp
-
Each puzzle instance will be provided
as an ASCII file masyuX.txt with the following format.
Each line contains n points separated by blank
spaces (that is, each line has 2*n-1 characters
followed by a newline). A dot "." represents a regular
grid point without any restriction, a "0" represents a
white circle and "1" a black circle. As an example,
the input file for the scenario in the picture above
could look like:
1 . . . . .
. . . . 0 .
1 0 . . . .
. . . . 0 0
. . 1 . . .
. 0 . . 0 .
|
Note that we leave one blank space
between each two columns and one blank line (with
2*n-1 blank spaces) between each two rows. You will
use the python program encode.py that takes the
masyuX.txt file as an input and creates an masyuX.lp
file describing the instance as a set of ASP facts of
the form "black(N)" or "white(N)" where N is the
number of a point from 0 to n x n - 1, browsing from
top to down and from left to right. An example of use
could be:
python3 encode.py masyu02.txt
masyu02.lp
getting the set of facts
#const n=6.
black(0;12;26).
white(10;13;22;23;31;34).
-
Finally, we will translate back the
answer set into a complete Masyu solution, printing
the final result in standard output. The solution will
be just a copy of the input file where we have filled
the edges with horizontal "-" or vertical "|" lines as
shown below:
1-.-.-.-.-.
|
|
. . . .-0-.
| |
1-0-. . .-.
| | | |
. . . . 0 0
| | | |
.-.-1 .-. .
|
|
.-0-.-.-0-.
|
To print this output we can use the
python program decode.py as follows:
python3
decode.py masyuKB.lp masyu02.lp >
solution02.txt
This program uses the predicate "seg(N,M)" that tells
us that we must draw a segment between the adjacent
points N and M, where N and M are point numbers using
the same numeration as in the input masyu02.lp
-
. The following files have been
added or updated
- encode.py
: It now takes the input and output file names as
arguments. It does not use standard input "<" or
standard output ">" any more
- decode.py
: The previous version was expecting a fact
"size(n)." to find out the size of the grid. This
fact is now added automatically before drawing
- masyu-examples.zip
: This zip file includes now two new instances,
masyu07.txt (size=20) and masyu08.txt (size=25) with
their respective solutions.
- drawmasyu.lp
: You can use this code together with the python
program display.py for a
graphical visualization of your puzzle solution. As
an example of use:
python3
display.py masyuKB.lp masyu02.lp
drawmasyu.lp
Additional comments
- For simplicity, we can assume that the number of
rows and columns coincide (square grids of n x n,
where n >=0)
- These are some problem instances and their
solutions: masyu-examples.zip
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 with your names and describing how
to use the code, if needed.
Deadline:
- Grado en
Inteligencia Artificial: May 9 2024
(23:59)
- Grado en
Ingeniería Informática: May 13, 2024
(23:59)
Assignments may be required to pass
through a defense process. If this is the case, it
will be announced in the first, preliminary list of
grades.
|
|