KR: Exercise 1

Stitches puzzle

Shingoki example
                       
Shingoki example
Initial configuration. M=1
Solution


Introduction

In this exercise we will use clingo to find solutions to the Stitches puzzle. The initial state is an empty square grid of N x N cells that is organized in irregular regions of adjacent cells. For instance, in the example above, we have a 5 x 5 grid with 5 regions of different numbers of cells: from top to down, left to right, regions of sizes 2, 7, 4, 3, 9. The goal of the puzzle is placing stitches: a "stitch" is a vertical or horizontal connection of two adjacent cells. Each cell connected by a stitch is called a "hole". The constraints of the puzzle are as follows:

  1. Each stitch must connect two different regions and all stitches must be connected forming a cyclic path
  2. Two stitches cannot share a hole from a third region
  3. Every pair of adjacent regions must be connected by a fixed number M>0 of stitches plus regions
  4. The numbers in the upmost row indicate the total number of holes per each column
  5. The numbers in the leftmost column indicate the number of holes per each row and the number of holes must be smaller than the number of regions
Each puzzle has two parameters: N>1 is the size of the grid; and M>0 is the number of stitches that must connect each pair of adjacent regions. In the example above, for instance, we have M=1 stitch connecting each pair of adjacent regions.

Steps

  1. Encode the Stitches problem as an ASP program that solves the puzzle for any instance. This program is our Knowledge Base and will be called stitches.lp

    NOTE: student groups will use one of the different notations to refer the cell positions in the grid
    Type 0: denote each cell position as a pair (X,Y) where X is the row, from the upmost row 0 to the lowest row N-1, and Y is the column, from leftmost 0 to N-1 rightmost.

    Type 1: denote each cell with a unique integer number from 0 to (N x N)-1 going from up to down and left to right. For instance, in the example with N=5, the first row would be positions 0..4 from left to right, the second row 5..9 etc until the last row 20..24.

    Type 2: denote each cell position as a pair (X,Y) where X is the column from 1 (the leftmost column) to N (the rightmost column) and Y is the row from 1 (the lowest row) to N (the upmost row).

    To know which type you belong to: from the two students forming the group, take the last name of the one alphabetically lower and count the number of letters, making modulo 3. Example, if the students last names are "Fernández López" and "Johnson", the alphabetically lower is "Fernández" the total number of letters is 9 and 9 modulo 3 is = Type 0. As another example, if the students last names are "Pérez Ruiz" and "Gómez García" the lower last name is "Gómez" = 5 letters and 5 modulo 3 = Type 2.

  2. Each puzzle instance will be provided as an ASCII file domXX.txt with the following format. The first line contains the two numbers N and M. Then, we have a grid of N x N characters where each letter a, b, c, d, etc, in the grid means that the corresponding cell belongs to a region named with that letter. Finally, we have two lines of N numbers corresponding to number of holes per column and number of holes per row, respectively.  As an example, the input file for the initial configuration in the picture above could look like:

    5 1
    aabbc
    bbbbc
    dbecc
    ddeee
    eeeee
    2 3 3 2 2
    2 2 4 3 1

    You will create a python program called encode.py that takes each domXX.txt file as an input and creates an domXX.lp file describing the instance as a set of ASP facts using your representation of the problem. An example of use could be:

            python3 encode.py dom02.txt dom02.lp

    Warning: domain files domXX.lp can only contain facts and constants. Other rules or constraints are not allowed in domain files.

  3. Finally, we will translate back the answer set into a complete Stitches solution, using the following notation:
  • ">" followed by "<" denotes an horizontal stitch
  • "v" with "^" below denotes a vertical stitch
  • "." denotes an empty cell without holes
As an illustration, the solution in the example puzzle above corresponds to the output file
.><..
..vv.
.v^^v
v^..^
^....

To print this output you will build the a python program decode.py to be used as follows
 
   python3 decode.py stitches.lp dom02.lp sol02.txt

As a starting point to create this file, you can use the example decodeexample.py that retrives in python the arguments of two predicates "q(N)" where N is a number and "p(X,N)" where X is a string and N is a number. To see its effect, use it for instance with the logic program (program.lp):

   q(1..5).
   p((a;b;c), 1..3).

and call python3 decodeexample.py program.lp

NEW: examples.zip containing a benchmark with several domains and their unique solutions.

Assessment and Delivery

The maximum grade for this exercise is 1.5 points = 15% of the course.

Warning: exercises must be made by groups of 2 students. If you do not have an assignment companion, please contact with Pedro Cabalar to organize a matching or find an alternative. Individual assignments submitted without the professor's permission will be automatically rejected.

Delivery: upload the assignment in a single .zip file containg

  • a README.txt file with your names, the position encoding type you got assigned (0, 1, or 2) and any additional remark needed to execute the code, if needed.
  • The files stitches.lp, encode.py and decode.py
  • If you have tried multiple versions of stitches.lp you can include them and comment their meaning in the README.txt
  • DO NOT INCLUDE: example files or other support material already contained in the current web page

Deadline: April 10th 2026 (23:59).

IMPORTANT: Assignments may be required to pass through a defense exam. If this is the case, it will be announced in the first, preliminary list of grades. The defense exam will consist of multiple questions about the submitted assignment to explain code, fill missing parts or make small variations.
Maintained by Pedro Cabalar.