light.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem Description.\n",
    "\n",
    "The task of this project is to solve a logic [puzzle](https://www.janko.at/Raetsel/Akari/) in which a two-dimensional playing field is to be illuminated with lights using ASP.\n",
    "\n",
    "The playing field is a square grid with a few cells predetermined. The given cells are either empty or contain an integer between 0 and 4.\n",
    "\n",
    "The goal of the puzzle is to place lights on the non-predetermined cells so that each non-predetermined cell is illuminated by (at least) one light horizontally or vertically, with light rays not shining through predetermined (empty or containing a number) cells.\n",
    "\n",
    "Additional constraints are that no two lights may illuminate each other and that for each cell with a number ``n``, exactly ``n`` horizontally or vertically adjacent cells must each contain a light.\n",
    "\n",
    "One example is shown in the next figure.\n",
    "![A light puzzle and its solution](img/light.png)\n",
    "\n",
    "The left side shows the playing field with eight predetermined cells, three of which are empty and five of which each contain a number. On the right side the lights are also shown, the placement of which forms a solution for the puzzle.\n",
    "\n",
    "Observe that each non-given (white) cell either contains a light or has a horizontal or vertical connection to a cell with a light.\n",
    "\n",
    "However, there are no such connections between the cells with lights, e.g. cells (4,4) and (4,6) are separated from each other by the cell with the number 2.\n",
    "\n",
    "Last but not least, each given cell with a number has the required number of horizontally or vertically adjacent cells with lights."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Representation in ASP.\n",
    "We represent the size of the grid, the predetermined cells with numbers and the empty predetermined cells using the following facts:    \n",
    "\n",
    "```\n",
    "rows(R).      % Number of rows\n",
    "cols(C).      % Number of columns\n",
    "digit(X,Y,D). % Digit D at position (X,Y), i.e., in row X and column Y\n",
    "empty(X,Y).   % Empty cell at position (X,Y), i.e., in row X and column Y\n",
    "```\n",
    "For instance, the example shown in the previous figure is represented by the following facts:\n",
    "\n",
    "```\n",
    "rows(6).      cols(6).\n",
    "digit(1,3,1). digit(3,2,0). digit(4,5,2). digit(6,3,0). digit(6,4,1).\n",
    "empty(1,4).   empty(3,5).   empty(4,2).\n",
    " ``` \n",
    " \n",
    "A solution, i.e. a placement of lights on non-predetermined cells, which satisfies all the conditions described above, is represented by atoms of predicate light/2:\n",
    "```\n",
    "light(X1,Y1) light(X2,Y2) ... light(Xn,Yn) % Cells with lights\n",
    "```\n",
    "\n",
    "For instance, the solution of the previous figure consists of the following atoms:\n",
    "```\n",
    "light(1,1) light(1,5) light(2,3) light(4,4) \n",
    "light(4,6) light(5,2) light(6,5)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Framework.\n",
    "\n",
    "The directory ``asp`` contains the files that you need for the project. In the directory ``asp/instances`` you can find the instances, and in the directory ``asp/solutions`` you can find their solutions in ``json`` format. \n",
    "\n",
    "You have to submit a file named ``light.lp``, included as a template in the directory ``asp``, that contains the following line (and no more ``#show`` statements) so that in the output only the atoms of predicate ``light/2`` appear:\n",
    "\n",
    "``#show light/2.``\n",
    "\n",
    "You can check if your encoding solves correctly all instances by running the ``Python`` script ``test.py`` as follows:\n",
    "* ``python asp/test.py -e asp/light.lp -i asp/instances -s asp/solutions -t 100``\n",
    "\n",
    "In this case, the timeout for each instance is set to `100` seconds, but you can use any other value instead.\n",
    "\n",
    "We recommend you to work locally in your computer, using your own installation of ``clingo``.\n",
    "\n",
    "For this, you can run the next cell to generate a zip file of this directory. The zip file will be stored in the parent directory with the name `light.zip`. You can click on the folder symbol at the left of the screen to look for it and download it.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "from shutil import make_archive\n",
    "make_archive('../light', 'zip', os.getcwd())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also run your encoding in the next cell. It is not recommended to work in this notebook at ``Binder``, but if you do it, 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 asp/instances/ex01.lp -\n",
    "\n",
    "% Your implementation please...\n",
    "\n",
    "\n",
    "\n",
    "#show light/2."
   ]
  },
  {
   "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",
    "Your solution has to correctly encode all solutions for every instance. \n",
    "In fact, our test instances usually have several solutions. \n",
    "This is tested automatically by the script ``test.py``. \n",
    "\n",
    "We will send you further instructions about the submission process from Moodle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tips:\n",
    "* Think about which conditions you want to test to characterize solutions and define suitable predicates that enable these tests.\n",
    "* Commands to find all answer sets look as follows:\n",
    "\n",
    "> ``clingo light.lp instance.lp 0``\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",
    "* 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."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}