yosenabe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem Description.\n",
    "\n",
    "The task of this project is to solve the\n",
    "Japanese grid puzzle [Yosenabe](http://www.nikoli.co.jp/en/puzzles/yosenabe.html)\n",
    "using ASP.\n",
    "To illustrate the rules of the game, consider a grid as follows:\n",
    "<img width=\"230\" height=\"150\" src=\"img/yosenabe.png\">\n",
    "\n",
    "Given such a grid, initially without arrows,\n",
    "the task is to move each number surrounded by a frame into one\n",
    "of the gray areas along a straight line, respecting the following conditions:\n",
    "* The straight lines of any two moved numbers \n",
    "  must not cross or meet at any grid cell.\n",
    "* Each gray area must be populated with at least one moved number.\n",
    "* An area may be associated with a positive goal number, shown within it.\n",
    "  If this is the case, then the numbers moved into the area must sum up exactly to the goal number.\n",
    "\n",
    "The unique solution of the example, indicated by the arrows of the image,\n",
    "fulfills these conditions:\n",
    "* The straight lines do not cross or meet.\n",
    "* Some number is moved into each of the four gray areas.\n",
    "* The bottom left area is associated with goal number ``6``, \n",
    "  and the numbers ``5`` and ``1``, that add up to ``6``, are moved to it.\n",
    "  The top right area is associated with goal number ``4``, \n",
    "  and exactly number ``4`` is moved to it.\n",
    "\n",
    "Note that the displayed solution is unique.\n",
    "One could try to move the two numbers ``2`` into the top right area, but \n",
    "that would leave the bottom right area unoccupied.\n",
    "\n",
    "A number can be moved across an area.\n",
    "For instance, in our example the number ``4`` crosses the area in the middle.\n",
    "On the other hand, you may always assume that the move of a number stops at the first cell (with respect to its direction)\n",
    "of the area to which the number is moved.\n",
    "For instance, number ``1`` is moved to the cell ``(2,1)``, and \n",
    "there would be no solution if we moved it further into the area until the cell ``(1,1)``.\n",
    "<!--\n",
    "That is, regardless of the cell to which number ``5`` is moved,\n",
    "it cannot help to move ``1`` to the cell in the lower left corner\n",
    "as the move enters the same area already before.\n",
    "-->\n",
    "You can play the game [here](http://www.janko.at/Raetsel/Yosenabe/).\n",
    "It is fun and it will help you to get used to the rules."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Representation in ASP.\n",
    "\n",
    "A Yosenabe puzzle is represented by facts of the following predicates:\n",
    "```\n",
    "cell(X,Y).         % the cell (X,Y) belongs to the grid\n",
    "area(X,Y,A).       % the cell (X,Y) belongs to area A\n",
    "number(X,Y,N).     % the cell (X,Y) initially contains number N\n",
    "goal(A,G).         % the goal number of area A is G\n",
    "```\n",
    "\n",
    "The example shown before is represented by the following facts:\n",
    "```\n",
    "cell(1,1).    cell(1,2). ...  cell(5,4).  cell(5,5).  number(1,5,5).\n",
    "area(1,1,1).  area(2,1,1).                goal(1,6).  number(3,1,1).\n",
    "area(2,3,2).  area(3,3,2).  area(4,3,2).              number(3,4,2).\n",
    "area(3,5,3).  area(4,5,3).  area(5,5,3).  goal(3,4).  number(4,2,4).\n",
    "area(5,1,4).                                          number(5,3,2).\n",
    "```\n",
    "\n",
    "A solution is represented by atoms of the predicate ``target/4``:\n",
    "```\n",
    "target(X,Y,XX,YY).  % the number in the cell (X,Y) is moved to the cell (XX,YY)\n",
    "```\n",
    "\n",
    "The solution of the example consists of the following atoms:\n",
    "```\n",
    "target(1,5,1,1) target(3,1,2,1) target(3,4,3,3) target(4,2,4,5) target(5,3,5,1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Task.\n",
    "\n",
    "Write an ASP encoding such that given an instance,\n",
    "the stable models of the encoding and the instance\n",
    "correspond to the solutions of the problem represented by the instance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Framework.\n",
    "\n",
    "In the directory ``instances`` you can find 14 instances (our example is ``instances/instance01.lp``). You have to submit a file named ``yosenabe.lp``, included as a template in this directory, that contains the following line (and no more ``#show`` statements) so that in the output only the atoms of predicate ``target/4`` appear:\n",
    "\n",
    "``#show target/4.``\n",
    "\n",
    "Click the link at the following cell to download a zip file with the instances and the template. We recommend you to work with them in your own computer, using your own installation of ``clingo``.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<a href='yosenabe.zip' target='_blank'>yosenabe.zip</a><br>"
      ],
      "text/plain": [
       "/home/jovyan/projects/yosenabe/yosenabe.zip"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import FileLink\n",
    "FileLink(\"yosenabe.zip\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, you can also run your encoding in the next cell, but this is not the recommended option. If you work in this notebook, remember to download the files that you modify to your computer, otherwise you will lose your changes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%clingo 0 instances/instance01.lp -\n",
    "\n",
    "\n",
    "dir(0,1). dir(0,-1). dir(1,0). dir(-1,0).\n",
    "\n",
    "% Hints:\n",
    "% - You may use the gaps of adjacent cell coordinates to denote directions.\n",
    "% - Develop your encoding incrementally and check the additions.\n",
    "% - You can use the \"--text\" option of clingo to inspect the ground program.\n",
    "%   For this it is better to use small instances.\n",
    "\n",
    "\n",
    "% Your encoding please...\n",
    "\n",
    "\n",
    "#show target/4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Formalities.\n",
    "You can work on the solution alone or in groups of two people. \n",
    "Different groups have to submit different solutions, in case\n",
    "of plagiarism all groups involved will fail the project. \n",
    "\n",
    "We will test your encoding with the 14 provided instances.\n",
    "Your solution has to correctly encode all solutions for every instance\n",
    "(in this case, all instances have a unique solution).\n",
    "This will be tested automatically. \n",
    "Please contact us if you get stuck."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tips:\n",
    "      \n",
    "* The directions between adjacent cells (up, down, left, and right) are \n",
    "entirely symmetric and vary only by coordinate differences between the cells. \n",
    "Please avoid code duplication due to referring to directions more specifically than needed. \n",
    "It is not a good idea to distinguish directions by using atoms such as \n",
    "``goUp(X,Y,X,Y+1)``, ``goDown(X,Y,X,Y-1)``,\n",
    "``goRight(X,Y,X+1,Y)``, and ``goLeft(X,Y,X-1,Y)``.\n",
    "On the other hand, it is a good idea to use atoms like \n",
    "``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\n",
    "``go(X,Y,X-1,Y,-1,0)`` because they can be treated uniformly within rules.      \n",
    "\n",
    "* 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.\n",
    "\n",
    "* 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.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}