sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem Description.\n",
    "\n",
    "The task of this project is to solve a Sudoku puzzle using ASP. The goal of the game is to fill a 9x9 grid with digits so\n",
    "that each column, each row and each of the nine 3x3 sub-grids that compose the grid contains all numbers from 1 to 9.\n",
    "In other words, the grid has to be filled with numbers from 1 to 9 so that the same number does not appear\n",
    "twice in the same row, column or in any of the nine 3x3 sub-grids of the 9x9 playing board.\n",
    "Initially the grid is partially filled.\n",
    "\n",
    "One example is shown in the next figure. The left side shows the initial configuration, and the right side shows the same puzzle with solution numbers marked in red.\n",
    "![A sudoku and its solution](img/sudoku.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Representation in ASP.\n",
    "The initial state of the grid is represented by facts of predicate ``initial/3``:    \n",
    "\n",
    "``initial(X,Y,N). % initially cell [X,Y] contains number N``\n",
    "\n",
    "For instance, the example shown in the previous figure is represented by the following facts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%file asp/instances/ex00.lp\n",
    "initial(1,1,5). initial(1,2,3). initial(1,5,7).\n",
    "initial(2,1,6). initial(2,4,1). initial(2,5,9). initial(2,6,5).\n",
    "initial(3,2,9). initial(3,3,8). initial(3,8,6).\n",
    "initial(4,1,8). initial(4,5,6). initial(4,9,3).\n",
    "initial(5,1,4). initial(5,4,8). initial(5,6,3). initial(5,9,1).\n",
    "initial(6,1,7). initial(6,5,2). initial(6,9,6).\n",
    "initial(7,2,6). initial(7,7,2). initial(7,8,8).\n",
    "initial(8,4,4). initial(8,5,1). initial(8,6,9). initial(8,9,5).\n",
    "initial(9,5,8). initial(9,8,7). initial(9,9,9)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution is represented by atoms of predicate sudoku/3:  \n",
    "\n",
    "``sudoku(X,Y,N). % the cell [X,Y] contains number N``   \n",
    "\n",
    "For instance, the solution of the previous figure consists of the following atoms:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "``\n",
    "sudoku(1,1,5) sudoku(1,2,3) ... sudoku(1,8,1) sudoku(1,9,2)\n",
    "...\n",
    "sudoku(9,1,3) sudoku(9,2,4) ... sudoku(9,8,7) sudoku(9,9,9)\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 ``sudoku.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 ``sudoku/3`` appear:\n",
    "\n",
    "``#show sudoku/3.``\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 asp/sudoku.lp 100 SAT``\n",
    "\n",
    "In this case, the timeout for each instance is set to `100` seconds, but you can use any other value instead.\n",
    "We have tested the script with `Python` version `3.6`.\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 `sudoku.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('../sudoku', '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/ex00.lp -\n",
    "\n",
    "subgrid_size(3).\n",
    "\n",
    "% Hints:\n",
    "% - For subgrid_size(s), subgrids can be identified by labels 0..s*s-1\n",
    "% - A cell (x,y) can be mapped to the subgrid labeled (((x-1)/s)*s + (y-1)/s)\n",
    "\n",
    "% Your encoding please...\n",
    "\n",
    "#show sudoku/3."
   ]
  },
  {
   "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",
    "* To begin with, it may be easier to represent a 4x4 Sudoku and once this is done, modify it to handle the 9x9 case.\n",
    "* Commands to find all answer sets look as follows:\n",
    "\n",
    "> ``clingo sudoku.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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}