KR: Exercise 1

Masyu puzzle

Shingoki example
                       
Shingoki example
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:

  1. All edges must form a single, linear loop. No crossing or branching is allowed.
  2. The loop must pass through all circles.
  3. 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)
  4. 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

  1. 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

  2. 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).

  3. 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

  4. NEW: (May 7th). 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.
Maintained by Pedro Cabalar. Last update May 7th, 2024