{
"nbformat_minor": 2,
"nbformat": 4,
"cells": [
{
"source": [
"$$\n",
"\\def\\CC{\\bf C}\n",
"\\def\\QQ{\\bf Q}\n",
"\\def\\RR{\\bf R}\n",
"\\def\\ZZ{\\bf Z}\n",
"\\def\\NN{\\bf N}\n",
"$$\n",
"# Tiling by polyominos\n",
"\n",
"Authors \n",
"- Thierry Monteil\n",
"\n",
"License \n",
"CC BY-SA 3.0\n",
"\n",
"This tutorial aims at exploring some ways to experiment on tilings of polyominos, and survey some generic tools which could serve in other circumstances. The methods involve integer programming, using SAT solvers, dancing links, Groebner bases, graph theory, Markov chains, and are all easily used in Sage.\n",
"\n",
"In this tutorial, a *polyomino* is just a finite subset of $\\mathbb{Z}^2$. A set `S` of (small) polyominos is said to *tile* a given (big) polyomino `P` if `P` can be written as a disjoint union of translated copies of elements of `S`.\n",
"\n",
"The sections are independent, do not hesitate to skip some of them or solve them in your prefered order.\n",
"\n",
"## Landscape setup\n",
"\n",
"Define quickly a class `Polyomino` and add some manipulation tools, for example, you can define some of the following methods (at least `__init__`, `plot`, and then write the ones when you need them):\n",
"\n",
"> - `__init__` to create a polyomino from an iterable of points.\n",
"> - `shift` to translate the polyomino.\n",
"> - `plot` to plot the polyomino.\n",
"> - `check` to check that what you created is actually a polyomino (this is useful to make checks in the `__init__` method optional (set to `True` by default)).\n",
"> - `__hash__` to be able to put the polyomino in a set or a dictionary.\n",
"> - `__repr__` to give a string representaton of the polyomino.\n",
"> - `__add__` to be able to make the union of polyominos, or the translate of a polyomino by an element of $\\mathbb{Z}^2$.\n",
"> - `__eq__` to be able to check equality between two polyominos.\n",
"> - `swap` to swap the polyomino with respet to the diagonal $x=y$.\n",
"> - `rotate` to rotate the polyomino by $\\pi/2$.\n",
"> - `__contains__` to check if an element of $\\mathbb{Z}^2$ belongs to the polyomino.\n",
"> - `__iter__` to provide all points of the polyomino one by one.\n",
"\n",
"Define also a `Tiling` class that represents a finite set of translated polyominos."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"You could let those two classes inherit from `SageObject` so that you can save them easily on a file.\n",
"\n",
"Alternatively, you can download the file `polyomino.sage` which belongs to this directory and start from there.\n",
"\n",
"## Tiling with a single tile\n",
"\n",
"The problem of tiling a polyomino `P` with a single polyomino `Q` can be solved in quasi-linear by noticing the following: the lower-left position of `P` must covered by the lover-left position of one of the copies of `Q` that belongs to the tiling.\n",
"\n",
"Hence, it suffice to see if a copy of `Q` located at this position is included in `P` and iterate.\n",
"\n",
"Implement a `is_singly_tileable` method for polyominos that implement this strategy and decides whether the polyomino is tileable by another given polyomino."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Add a `certificate` option to the `is_singly_tileable` method such that, when set to `True`, the method returns a correct tiling instead of just `True`."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"See how far you can go on some examples."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## A NP-hard problem\n",
"\n",
"Deciding whether a polyomino can be tiled by a given list of polyominos is NP-hard. It is not a reason not to try anyway.\n",
"\n",
"For each of the following technique, implement a `is_tilable_` method that decides whether a given set of polyominos tiles the polyomino. Add a `certificate` option which, when set to `True` returns an acceptable tiling instead of a boolean. When possible, add a `all` option, which, when set to `True` iterates over all solutions.\n",
"\n",
"You can implement some of the following methods and compare them (both in execution time, and in development time):\n",
"\n",
"### Brute force\n",
"\n",
"Try every combination of positions of the small polyominos, select the ones that satisfy the tiling condition."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"### Backtrack\n",
"\n",
"Start to place polyominos one by one, backtrack when you are locked. See also the `backtrack` worksheets for other examples of this method."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"### Dancing Links\n",
"\n",
"You can use Knuth's dancing-links algorithm, see \n",
"\n",
"Dancing links are implemented in Sage:"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"from sage.combinat.matrices.dancing_links import dlx_solver"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"### Integer Linear Programming\n",
"\n",
"Try to express the tileability as an integer linear program, and let Sage solve it for you.\n",
"\n",
"*Hint:* see the MILP tutorial.\n",
"\n",
"*Hint:* a default solver is provided in Sage, you can install a faster solver, for example `cbc`."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"MixedIntegerLinearProgram?"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"*Hint;* note that the solver will only return a single solution. If you want to iterate over all solutions, you can get the polytope correspoding to your linear program, and request its integer points.\n",
"\n",
"### SAT solver\n",
"\n",
"Try to express the tileability as a `SAT` formula, and let Sage solve it for you.\n",
"\n",
"*Hint* install the `cryptominisat` optional package."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"S = SAT()\n",
"S?"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"### Constraint satisfaction solver\n",
"\n",
"Beyond inear constraints, there exists CSP solvers that understand a larger set of types of constraints (e.g. that allow to express injectivity easily). Unfortunately, Sage does not provides CSP solvers by default. If you know such solver that is interfaced with Python, you can install it with the `sage -pip` command and compare its behaviour with the previous methods."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## An algebraic necessary condition\n",
"\n",
"An *ideal* `I` of a multivariate polynomial ring `R` is a subset of `R` which is stable by internal addition and by multiplication by elements of `R`.\n",
"\n",
"To a polyomino `P` included in $\\mathbb{N}^2$ we associate a polynomial `P.poly()` with coefficients in a given `ring`, as the sum of the monomials `x^i y^j` for all `(i,j)` in `P`.\n",
"\n",
"What is the polynomial associated to a translated copy of a polyomino ?\n",
"\n",
"Prove that if a polyomino `P` is tilable by a set `S` of polyominos, then `P.poly()` belongs to the ideal generated by the set of `s.poly()` for `s` in `S`.\n",
"\n",
"Implement a `is_poly_tileable(self, S, ring, certificate=False)` that check this nececessary condition. When certificate is set to `True`, let the method return a linear combination of translated small polyominos that \"algebraically\" tiles the big polyomino.\n",
"\n",
"*Hint:* look at the `lift` method for polynomials w.r.t ideals."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Thanks to Groebner bases, deciding whether a given polynomial is an element of a given ideal is practically pretty fast.\n",
"\n",
"Actually, ideal containment depends on the ring on which the polynomial is defined. Give an example of a pair `(P,S)` that is polynomially tileable over `QQ` but not over `ZZ`, and a pair `(P,S)` that is polynomially tileable over `ZZ` but not over `NN`."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## Tetris\n",
"\n",
"See how the various algorithms behave, and how far you can go with each of them. You can also combine them to get a faster one.\n",
"\n",
"Test your algorithms on the Tetris game, that is tile a 10x22 rectangle with the connected polyominos with 4 points.\n",
"\n",
"*Hint* to save you some time, you can use the following:"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"tetris_patterns = [Polyomino([(0,0),(1,0),(2,0),(3,0)]),\n",
" Polyomino([(0,0),(1,0),(2,0),(0,1)]), \n",
" Polyomino([(0,0),(1,0),(2,0),(1,1)]),\n",
" Polyomino([(0,0),(1,0),(1,1),(2,1)]),\n",
" Polyomino([(0,0),(1,0),(0,1),(1,1)])]"
],
"outputs": [],
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## Tiling with dominos\n",
"\n",
"The problem of tiling a polyomino `P` with a given set of tiles becomes polynomial when the set of tiles is the pair of dominos `{{(0,0),(1,0)}, {(0,0),(0,1)}}`.\n",
"\n",
"Indeed, if we consider the underlying grid-graph `G` whose vertices are elements of `P` and whose edges connect vertices at distance 1, the problem is equivalent to know whether there exists a perfect matching in the (bipartite) graph.\n",
"\n",
"Implement a `is_domino_tileable` method for polyominos (with a `certificate` option as before), and see how far you can go in tiling large shapes."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"## The Aztec diamond\n",
"\n",
"Among the shapes to be tiled by dominos, let us study the case of the Aztec diamond, that is, the integer points included in a square rotated by $\\pi/2$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"Here are the first five Aztec diamonds:\n",
"\n",
" **\n",
" **\n",
"\n",
"\n",
" **\n",
" ****\n",
" ****\n",
" **\n",
"\n",
"\n",
" **\n",
" ****\n",
" ******\n",
" ******\n",
" ****\n",
" **\n",
"\n",
"\n",
" **\n",
" ****\n",
" ******\n",
" ********\n",
" ********\n",
" ******\n",
" ****\n",
" **\n",
"\n",
"\n",
" **\n",
" ****\n",
" ******\n",
" ********\n",
"**********\n",
"**********\n",
" ********\n",
" ******\n",
" ****\n",
" **"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Draw a domino tiling of the Aztec diamond obtained by the algebraic method, the MILP and SAT methods, and the other methods you implemented.\n",
"\n",
"Which patterns appear in the methods that took care of the geometry (in particular, the polynomial algorithm for perfect matching to Edmonds), and which patterns appear in the other methods (e.g. the MILP method with various solvers) ?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"In how many ways can the n-th Aztec diamond be tiled by dominos ?\n",
"\n",
"*Hint:* compute the first values and use the On-Line Encyclopedia of Integer Sequences:"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"oeis?"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"To understand, which of the patterns we found are generic, we want to sample uniformly a random tiling of the Aztec diamond by dominos, without enumerating all those tilings first. For this, implement and run the Markov chain that randomly chooses a position `(i,j)` in the Aztec diamond and rotates the polyominos as follows whenever possible (otherwise chose another position, and iterate):"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"The * is the point with coordinates (i,j)\n",
"\n",
"+--+--+ +--+--+\n",
"| | | | |\n",
"+ + + -> +--+--+\n",
"|* | | |* |\n",
"+--+--+ +--+--+\n",
"\n",
"And\n",
"\n",
"+--+--+ +--+--+\n",
"| | | | |\n",
"+--+--+ -> + + +\n",
"|* | |* | |\n",
"+--+--+ +--+--+"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Look at the pictures obtained after a lot of iterations !"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
}
],
"metadata": {
"kernelspec": {
"display_name": "sagemath",
"name": "sagemath"
}
}
}