{ "cells": [ { "cell_type": "markdown", "id": "f4805906", "metadata": { "tags": [ "CSP", "complex", "medium", "Extension", "starred" ] }, "source": [ "# Problem *Layout*" ] }, { "cell_type": "markdown", "id": "94571f1b", "metadata": {}, "source": [ "From \"Exploiting symmetries within constraint satisfaction search\" by P. Meseguer and C. Torras, Artificial Intelligence 129, 2001: given a grid, we want to place a number of pieces such that every piece is completely included in the grid and no overlapping occurs between pieces.\n", "See also [CSPLib--Problem 132](https://www.csplib.org/Problems/prob132)." ] }, { "attachments": { "layout.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAABEwAAAH0CAMAAAAQfkg3AAAJJmlDQ1BpY2MAAEiJlZVnUJNZF8fv8zzphUASQodQQ5EqJYCUEFoo0quoQOidUEVsiLgCK4qINEWQRQEXXJUia0UUC4uCAhZ0gywCyrpxFVFBWXDfGZ33HT+8/5l7z2/+c+bec8/5cAEgiINlwct7YlK6wNvJjhkYFMwE3yiMn5bC8fR0A9/VuxEArcR7ut/P+a4IEZFp/OW4uLxy+SmCdACg7GXWzEpPWeGjy0wPj//CZ1dYsFzgMt9Y4eh/eexLzr8s+pLj681dfhUKABwp+hsO/4b/c++KVDiC9NioyGymT3JUelaYIJKZttIJHpfL9BQkR8UmRH5T8P+V/B2lR2anr0RucsomQWx0TDrzfw41MjA0BF9n8cbrS48hRv9/z2dFX73kegDYcwAg+7564ZUAdO4CQPrRV09tua+UfAA67vAzBJn/eqiVDQ0IgALoQAYoAlWgCXSBETADlsAWOAAX4AF8QRDYAPggBiQCAcgCuWAHKABFYB84CKpALWgATaAVnAad4Dy4Aq6D2+AuGAaPgRBMgpdABN6BBQiCsBAZokEykBKkDulARhAbsoYcIDfIGwqCQqFoKAnKgHKhnVARVApVQXVQE/QLdA66At2EBqGH0Dg0A/0NfYQRmATTYQVYA9aH2TAHdoV94fVwNJwK58D58F64Aq6HT8Id8BX4NjwMC+GX8BwCECLCQJQRXYSNcBEPJBiJQgTIVqQQKUfqkVakG+lD7iFCZBb5gMKgaCgmShdliXJG+aH4qFTUVlQxqgp1AtWB6kXdQ42jRKjPaDJaHq2DtkDz0IHoaHQWugBdjm5Et6OvoYfRk+h3GAyGgWFhzDDOmCBMHGYzphhzGNOGuYwZxExg5rBYrAxWB2uF9cCGYdOxBdhK7EnsJewQdhL7HkfEKeGMcI64YFwSLg9XjmvGXcQN4aZwC3hxvDreAu+Bj8BvwpfgG/Dd+Dv4SfwCQYLAIlgRfAlxhB2ECkIr4RphjPCGSCSqEM2JXsRY4nZiBfEU8QZxnPiBRCVpk7ikEFIGaS/pOOky6SHpDZlM1iDbkoPJ6eS95CbyVfJT8nsxmpieGE8sQmybWLVYh9iQ2CsKnqJO4VA2UHIo5ZQzlDuUWXG8uIY4VzxMfKt4tfg58VHxOQmahKGEh0SiRLFEs8RNiWkqlqpBdaBGUPOpx6hXqRM0hKZK49L4tJ20Bto12iQdQ2fRefQ4ehH9Z/oAXSRJlTSW9JfMlqyWvCApZCAMDQaPkcAoYZxmjDA+SilIcaQipfZItUoNSc1Ly0nbSkdKF0q3SQ9Lf5RhyjjIxMvsl+mUeSKLktWW9ZLNkj0ie012Vo4uZynHlyuUOy33SB6W15b3lt8sf0y+X35OQVHBSSFFoVLhqsKsIkPRVjFOsUzxouKMEk3JWilWqUzpktILpiSTw0xgVjB7mSJleWVn5QzlOuUB5QUVloqfSp5Km8oTVYIqWzVKtUy1R1WkpqTmrpar1qL2SB2vzlaPUT+k3qc+r8HSCNDYrdGpMc2SZvFYOawW1pgmWdNGM1WzXvO+FkaLrRWvdVjrrjasbaIdo12tfUcH1jHVidU5rDO4Cr3KfFXSqvpVo7okXY5upm6L7rgeQ89NL0+vU++Vvpp+sP5+/T79zwYmBgkGDQaPDamGLoZ5ht2GfxtpG/GNqo3uryavdly9bXXX6tfGOsaRxkeMH5jQTNxNdpv0mHwyNTMVmLaazpipmYWa1ZiNsulsT3Yx+4Y52tzOfJv5efMPFqYW6RanLf6y1LWMt2y2nF7DWhO5pmHNhJWKVZhVnZXQmmkdan3UWmijbBNmU2/zzFbVNsK20XaKo8WJ45zkvLIzsBPYtdvNcy24W7iX7RF7J/tC+wEHqoOfQ5XDU0cVx2jHFkeRk4nTZqfLzmhnV+f9zqM8BR6f18QTuZi5bHHpdSW5+rhWuT5z03YTuHW7w+4u7gfcx9aqr01a2+kBPHgeBzyeeLI8Uz1/9cJ4eXpVez33NvTO9e7zofls9Gn2eedr51vi+9hP0y/Dr8ef4h/i3+Q/H2AfUBogDNQP3BJ4O0g2KDaoKxgb7B/cGDy3zmHdwXWTISYhBSEj61nrs9ff3CC7IWHDhY2UjWEbz4SiQwNCm0MXwzzC6sPmwnnhNeEiPpd/iP8ywjaiLGIm0iqyNHIqyiqqNGo62ir6QPRMjE1MecxsLDe2KvZ1nHNcbdx8vEf88filhICEtkRcYmjiuSRqUnxSb7JicnbyYIpOSkGKMNUi9WCqSOAqaEyD0tandaXTlz/F/gzNjF0Z45nWmdWZ77P8s85kS2QnZfdv0t60Z9NUjmPOT5tRm/mbe3KVc3fkjm/hbKnbCm0N39qzTXVb/rbJ7U7bT+wg7Ijf8VueQV5p3tudATu78xXyt+dP7HLa1VIgViAoGN1tubv2B9QPsT8M7Fm9p3LP58KIwltFBkXlRYvF/OJbPxr+WPHj0t6ovQMlpiVH9mH2Je0b2W+z/0SpRGlO6cQB9wMdZcyywrK3BzcevFluXF57iHAo45Cwwq2iq1Ktcl/lYlVM1XC1XXVbjXzNnpr5wxGHh47YHmmtVagtqv14NPbogzqnuo56jfryY5hjmceeN/g39P3E/qmpUbaxqPHT8aTjwhPeJ3qbzJqamuWbS1rgloyWmZMhJ+/+bP9zV6tua10bo63oFDiVcerFL6G/jJx2Pd1zhn2m9az62Zp2WnthB9SxqUPUGdMp7ArqGjzncq6n27K7/Ve9X4+fVz5ffUHyQslFwsX8i0uXci7NXU65PHsl+spEz8aex1cDr97v9eoduOZ67cZ1x+tX+zh9l25Y3Th/0+LmuVvsW523TW939Jv0t/9m8lv7gOlAxx2zO113ze92D64ZvDhkM3Tlnv296/d5928Prx0eHPEbeTAaMip8EPFg+mHCw9ePMh8tPN4+hh4rfCL+pPyp/NP637V+bxOaCi+M24/3P/N59niCP/Hyj7Q/Fifzn5Ofl08pTTVNG02fn3Gcufti3YvJlykvF2YL/pT4s+aV5quzf9n+1S8KFE2+Frxe+rv4jcyb42+N3/bMec49fZf4bmG+8L3M+xMf2B/6PgZ8nFrIWsQuVnzS+tT92fXz2FLi0tI/QiyQvpNzTVQAAAAgY0hSTQAAeiYAAICEAAD6AAAAgOgAAHUwAADqYAAAOpgAABdwnLpRPAAAAKVQTFRF////L4cHL4cHL4cHL4cHL4cHL4cHAABjAABjAABjeAY2eAY2L4cHL4cHAABjAABjL4cHL4cHL4cHAABjAABjeAY2eAY2L4cHL4gHAAAAAAAAAAAAAAAAL4cHL4cHAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAL4cHAABjeAY2AAAAHR0cOTk5Dg4OZGRj1tbVVlZVnZ2c////sWekWgAAACt0Uk5TAGa71uzIMzO7ZruIiEREiO/Z3czd3e7Hdbvs1ojqzUQiEZmqzFXddzPuZkzXAt8AAAABYktHRACIBR1IAAAACXBIWXMAAAEsAAABLABziOlSAAAAB3RJTUUH5QsRCh4VoSN/mAAAGMFJREFUeNrt3W1j6sh5gGF3m+Zlm6bJbpKWVC0vxhhoqz3ZJv//r1UYYyNAMCNmLGCu60tObB5jBnwbacD79AQAAADB/uG73v7xF7/4xT/1H//l0Dc92q9+PZTfDH3T430/lH8e+paX67f/PZR/GfqmR/vd/wzlX4e+6fH+dyjfD33LyyUm4cQkgpiUZxOTnscpv29G/9Bv9Ie7jcmP/Y5TfmxG/9h/9D5j8qeeByrN6J/7j4rJYDYx6Tn6b83ov/e/1vuMye/6j/YswhWjQ2p+rPuevbiiCGIyJDEJJyYRbjImo/7+8pe//MfXj16n+uL7XEzCiUmEm4xJXZbRF9/nYhJOTCKIyfDE5HaJSYRbjclP3/oZbPSvPUf/Kia3TEwi3GpMfv6/fgYb/dZz9JuY3DIxiSAmYhJBTOJGxSR8VEzEJOZaxST76JDEREwiiEncqJiEj4qJmMRcq5hkHx2SmIhJBDGJGxWT8FExEZOYaxWT7KNDEhMxiSAmcaNiEj4qJmISc61ikn10SGIiJhHEJG5UTMJHxURMYq5VTLKPDklMxCSCmMSNikn4qJiIScy1ikn20SGJiZhEEJO4UTEJHxUTMYm5VjHJPjokMRGTCGISNyom4aNiIiYx1yom2UeHJCZiEkFM4kbFJHxUTMQk5lrFJPvokMRETCKISdyomISPiomYxFyrmGQfHZKYiEkEMYkbFZPwUTERk5hrFZPso0MSEzGJICZxo2ISPiomYhJzrWKSfXRIYiImEcQkblRMwkfFRExirlVMso8OSUzEJIKYxI2KSfiomIhJzLWKSfbRIYmJmEQQk7hRMQkfFRMxiblWMck+OiQxEZMIYhI3Kibho2IiJjHXKibZR4ckJmISQUziRsUkfFRMxCTmWsUk++iQxERMIohJ3KiYhI+KiZjEXKuYZB8dkpiISQQxiRsVk/BRMRGTmGsVk+yjQxITMYkgJnGjYhI+KiZiEnOtYpJ9dEhiIiYRxCRuVEzCR8VETGKuVUyyjw5JTMQkgpjEjYpJ+KiYiEnMtYpJ9tEhiYmYRBCTuFExCR8VEzGJuVYxyT46JDERkwhiEjcqJuGjYiImMdcqJtlHhyQmZcbku35+34z+od/oD3cbkx9/3cuPzegf+4/eZ0z+9H0/zeif+4+KyaAxGcZ9xmQY9xmTYYiJmNwBMYkgJmXGpOdhzn82o//Vc7bxyyEf6r04zIngMKfMmFwxen9PL67gBGwEJ2DFJHJUTMJHxSR8NF9MfvrWz2Cjf+05+lcxuWViEuFWY1ISMbldYhJBTIYnJrdLTCKIyfDE5HaJSYRbjYkTsPmISTgxiSAmYhI5Kibho2ISPiomYvLYxCSCmIhJ5KiYhI+KSfiomIjJYxOTCGIiJpGjYhI+Kibho2IiJo9NTCKIiZhEjopJ+KiYhI+KiZg8NjGJICZiEjkqJuGjYhI+KiZi8tjEJIKYiEnkqJiEj4pJ+KiYiMljE5MIYiImkaNiEj4qJuGjYiImj01MIoiJmESOikn4qJiEj4qJmDw2MYkgJmISOSom4aNiEj4qJmLy2MQkgpiISeSomISPikn4qJiIyWMTkwhiIiaRo2ISPiom4aNiIiaPTUwiiImYRI6KSfiomISPiomYPDYxiSAmYhI5Kibho2ISPiomYvLYxCSCmIhJ5KiYhI+KSfiomIjJYxOTCGIiJpGjYhI+Kibho2IiJo9NTCKIiZhEjopJ+KiYhI+KiZg8NjGJICZiEjkqJuGjYhI+KiZi8tjEJIKYiEnkqJiEj4pJ+KiYiMljE5MIYiImkaNiEj4qJuGjYiImj01MIoiJmESOikn4qJiEj4qJmDw2MYkgJmISOSom4aNiEj4qJmLy2MQkgpiISeSomISPikn4qJiIyWMTkwhiIiaRo2ISPiom4aNiIiaPTUwiiImYRI6KSfiomISPiomYPDYxiSAmZcbku35+KDEmP/66lx+b0T/2H73PmPzp+36a0T/3HxWTQWNyheJiMoz7jMkwxERM7oCYRBCTMmPiMCfMr/odpyTwm6FveryexynXO3emRkyycgKWcohJVmJCOTY/mz/3M9joTz1HfxITyKcui5hALkP/dIvJuVEx4Y4M/dMtJudGxYQ7Ug91FrUa+pZ/CTGhHGKSlZhQDjHJSkwoh5hkJSaUQ0yyEhPKISZZiQnlEJOsxIRyiElWYkI5xCQrMaEcYpKVmFAOMclKTCiHmGQlJpRDTLISE8ohJlmJCeUQk6zEhHKISVZiQjnEJCsxoRxikpWYUA4xyUpMKIeYZCUmlENMshITyiEmWYkJ5RCTrMSEcohJVmJCOcQkKzGhHGKSlZhQDjHJSkwoh5hkJSaUQ0yyEhPKISZZiQnlEJOsxIRyiElWYkI5xCQrMaEcYpKVmFAOMclKTCiHmGQlJpRDTLISE8ohJlmJCeUQk6zEhHKISVZiQjnEJCsxoRxikpWYUA4xyUpMKIeYZCUmlENMshITyiEmWYkJ5RCTrMSEcohJVmJCOcQkKzGhHGKS1aYI3/Xzg5hwX8Qkq01MriAm3BExyUpMKIeYZCUmlENMsnIClnKISVZiQjmaH+tvP/dz3aiYBIyKCXekHoqYBIyKCXdETLISE8ohJlmJCeWonUXNSUwoh5hkJSaUQ0yyEhPKISZZiQnlEJOsxIRyiElWYkI5xCQrMaEcYpKVmFAOMclKTCiHmGQlJpRDTLISE8ohJlmJCeUQk6zEhHKISVZiQjnEJCsxoRxikpWYUA4xyUpMKIeYZCUmlENMshITyiEmWYkJ5RCTrMSEcohJVmJCOcQkKzGhHGKSlZhQDjHJSkwoh5hkJSaUQ0yyEhPKISZZiQnlEJOsxIRyiElWYkI5xCQrMaEcYpKVmFAOMclKTCiHmGQlJpRDTLISE8ohJlmJCeUQk6zEhHKISVZiQjnEJCsxoRxikpWYUA4xyUpMKIeYZCUmlENMshITyiEmWYkJ5RCTrMSEcohJVmJCOcQkKzGhHGKSlZhQDjHJSkwoh5hktSnCb/v5Tky4L2KS1SYmVxAT7oiYZCUmlENMshITyiEmWTkBSznEJCsxoRxNEb793I+YXCYmlKO+iphcICaUQ0yyEhPKISZZiQnlcAI2KzGhHGKSlZhQDjHJSkwoh5hkJSaUQ0yyEhPKISZZiQnlEJOsxIRyiElWYkI5xCQrMaEcYpKVmFAOMclKTCiHmGQlJpRDTLISE8ohJlmJCeUQk6zEhHKISVZiQjnEJCsxoRxikpWYUA4xyUpMKIeYZCUmlENMshITyiEmWYkJ5RCTrMSEcohJVmJCOcQkKzGhHGKSlZhQDjHJSkwoh5hkJSaUQ0yyEhPKISZZiQnlEJOsxIRyiElWYkI5xCQrMaEcYpKVmFAOMclKTCiHmGQlJpRDTLISE8ohJlmJCeUQk6zEhHKISVZiQjnEJCsxoRxikpWYUA4xyUpMKIeYZCUmlENMshITyiEmWYkJ5RCTrMSEcohJVmJCOcQkKzGhHGKS1aYIv+3nOzHhvohJVpuYXEFMuCNikpWYUA4xyUpMKIeYAEmICZBEU4RvP/cjJsCn+ipiArwTEyAJMQGScAIWSEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESEJMgCTEBEhCTIAkxARIQkyAJMQESKIpwref+xET4FN9FTEB3okJkISYAEk0Rfjb3/sRE+CT3RwgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSEBMgCTEBkhATIAkxAZIQEyAJMQGSaIrwt7/3IybAp/oqYgK8ExMgCTEBkhhfZTL0tw8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAIWbRn4c4ITp7LnjM8+zob834H5M5/Np/Kf2TMZVVY23F5y+DH1zgKE8L7qDMZ1fem4yfZ3X9Wg0mtezSfN/R6OOy00mhx9ZbobqauibDyRS1cszn11e+Gl/XdWL9VuMJrPV+um17ojJa12/HnxoUlUrMYGHMb7w41zV4+5PTp/3G7FcNXXoiEndOP7oWkzgYSxW58+KTFeL7s81hyn750iWzTONjpg0n1kdf3R8YzGZ9vpUsaYRHy3btMdn7s/rxZ/mqvsSo7petz7w0hmT5Xx+4mjqtmLSvav1ZGPrWNdyWalD5x5Yj7Rai/pSGqennlK8qY7TMeqKyWk3FZPzW1dhG1sF6VwQK3Xg7II80Gqt68thfD54+rEzqeuj8ykvdxyT912tajQ6+fyqc2NrPdr3XK0n+4s0eXpQ3ZuA/VbqcZfqaKVa+5jdG6b39sDqCkXrNtWnn6TN6vr4dMrqbmOy29VaV4vTB2tdG1vjqnpuurqqtjY75R+NPbGJdZ3xKu3Xu3q5TumzUkmXarL52qvR6038zj9eqfY+ZueG6Zc9sN6Wq55Xk6u+yrS+eJTz9gxkenr2xCqM7jUme7ta044zP2c2tponMx+/XybPn7fq9CZWb8vZrSzY+U3AHiuVcqnWq9nLePy6qFc38BLK0yu1v495bsP0Kx5Yr6uqyd20uvKx9VLP2ze8eY4/mh3eA4v61H3SLMeJj1fbH8PleF1V47e4bp76TMabF8m2rqj5xPSWYrK/q9URkzMbW6PWDfl8BJzexOqledK7Wi1uZcHObwL2WKmES7VebZ8KbDYbLz/xzu30Su0/8s9tmH7BA+t1Ptn+o6oDTnp0q1pHMNPRaD2evozqg42X55MP4OaqTzzTnU52t3qzCrNR8+uh2l52r6TrxWq2fqkW1e3EpLWr1bUn1b2x1b7PP88mnd7E6mVcvY6frv3tkcqlTcD4lUq3VJOPX/Snzup9tY6Vaj3yz2+YZn5gTVfzKslyjVq3YrTYfqlZvWp9o9XJn63R+SdazUFdVc02i/Z2qc1LUHbf/XO9PYE9nd/Oy+lbu1pdMene2Grf581Xq8/sMl/hVmJyaRNwyJWaff56ndVxGwIZdKxUKybdq/UFy7X5CX1//lZf9eha7T8NXDZfa/J22w5ex/p68rZeiEnznc2aY6jJ6v1IavRx6VG92wyb3kxM2rtanQ/BzvPVB/f5pbXp7UZicnkTcMCVWn3+LnzZPaQH07VS7efk3fsg+ZdrE5P3c7nXxaT1tGb8cdwya98F45M34HJM3lZo8n5K/SMm1d6plhv52Ti8Nztj0rWxVVpMLm8CDrhS9efdtxz8OKdrpdox6Vytr3hgPdej91/u9TVbRJP2Un8culXtj49P5j0gJtP2xd/+t3na8/k850Z+Ng53tTpjMuna/Tq+z1OdHmu7jQUL2AQccKVWe4cCQ8ekc6XGh+dCOhb0qx5YG8urnseNO5b6OCYnLvbcvurJ+MN2Xer2TtEuJuv9n9Tb+Nk42tV6+xaXVVW9Tg4ueHpj6+g+r7fnxQ83sdaz0Wi0/zWXm92z572XQxxd4sBtLNjhJuDx7YhdqcOlumalXkbPu8Oc8dAxOVqpjn3MrtX6sgfWxnW7OScq8VI9jxZ1SExe25daz+ud8fvtbv1638Wkap/GvoWfjcNdrc23PhktqvF6VI9CNrYO7/MmmG/7ge1NrPFiVS0n68XHE9/pc71Yj8frzd9uOH2JE9/oLSzYwXId3Y74lWovVYqVevNah7yQ6utWqnMfs2u1vuyB9fR2zHDNK/sPKzGZrern9Tjsmcnk+Ahr0mTo46XDHTEZ3WJM2rtazbe+eH+h6ctq1Vr/quMAqHWrlp+nAPc2sdbvH5zu7tLmc9tfBMv5dn2PLnHsNhasvVxHt6PXSu0tVZKV2l3ZsO+ja69U9z5m12p92QOr+eGd18/XhHfZrsR61fxG3t60w5ic2tMeHW9T7b+r5Z5ismov8udm2eZ3wf5SvHYcsu7dqsnmj7os9z7xsYjvX/OlXk2e3ray5q3ho0uccBsL1lquo9vRc6U+lirNSr1/pXOf/uqVOrOP2bVaX/TAGjfHI/XiygPC9oHKRxyOY3Jq+MS+W0BMbvIw5+Cp1/7pnnm9/zatjqXY3LrF29uxNu8JeR63PrH9x+Lz4bJ6u9Gfu1rv9/nRJU64jQVrLdfR7ei5Uh9LlWalNuZ1PfDr6TtW6uiO7FqtL3pgbc4Pzlar6qpDwv3Fbg6ZdseX25h8XO26+3FRHX3kUkxebvAE7OQoJp/fYvsdVeOO893NrZu3Tj+fuNkfT7ifN62afp6XXz7PpicuccpNLFhruY5uR9+V2i1VopXaLtbAr6Zvr9SZfcyu1fqyB9bT2zOaxTWvqh21f5XsfoS2MfkoSNcB3WR1ePwTEJOnG9waHp+Jybi1K9W1/zWqu08RvP3v/jv0qs3H1ocTR5c45SYWrLUI645bHr1Su6VKtFJvP0RDvzOne6WOY3L6IOOrHlgbTfpWV9Sk2js/tfdNzNsxmXWdxVqu6vafalgFxGS993ToRt4Eey4my9bLaXrHZHOC6f2t5NXbx46ycHSJU24vJl3fUe+YJFqp5sG5GrolZ1YqWUxSLdfGrD7zxOWidfun5v3Ni+O3d1tOP6523ln4pib77zd6DYlJ8y3vCrS+7vW7yZyLyVPrzFDvmGxeIFB9WJ84Rjy6xCm3F5NR6pgkWqmmJaneYpljpZLFJNFyvTn9hwBCTfZDtXvNyngx2Zx2rnZPR6ZnXhc32Xzruycn1Wq5q9Ny/No8Z1rvDvSW45emM+vx9uvM6u2bnl9Xz00KX8aD/wmb5YWYtM4EnHyIXrzPF4ePlqP7fBHy+qqbiMkyMCZxK7VbqjQrNV1ddfyffaWOY3L62/2CB9b7T+X2u7jm4TXfL9F6US+qaj6aPC03f2xs9yP0cva5z+bFaqNqPa5mq82+1fp5d4v2X8C2+7/v3+nLvHniNVvMJtXeZYZ0/pxJ+zDn5BcIeTbavpuOXm44CrkjbyImTwdP3k8eBEev1N5hzvUr9fmXVatBmxJxmNO5KHkfWPv/hYlxfdW7rNft65mMq5fJ9utOPj44u3Aea/I6e/sTlTH32uSl2lzD5iT1JGIsl4Nnd/tL+tJ6Nc26b0xeD+/Rl8Pj09d7isnncr10HGdHr9RuqVKs1N5faR72CcrBSnWegF33jsm1y7U5tNk9wK98ZnLujzztrFaDH4fkdvQK2Na9vtfSM6/rPH+fT/fv4ulm0Rd7R4+bDxxf4oTbiElruQ5vR9+V2i1VipWafzytnuR593avlTqzj3nuFbB5H1gv9eczmZf6ug2wKuDN5Dfw8M2saj8z3PtL2Qd/26VrY+vifd56IeDb37bc/yug69GpS5z8Rm/h3mgt19Ht6LlS+y9rvHKlPv880rS6/MvyK1eqax+zc8M0+wNrUs8/Xh1U7d4p1dP04p+Tv/Sf/HsE6/Y9tvmL4O//nLU3v7s2ti7f582/dl9pud1nmH2cdJusxicvcew2YrI+COzB7ei3Up9Lde1Kzeo9w/6ltcOV6trHnJ/5W1KZH1jVxxHh5mWr171i+OXiGy9v4C985zZpH7LWq8n272JOZ+03Up7c2JqMx+vVdu/q4JOtTazN19q+7Wr3+oeq3v5rvNh+4PgS+6bj7fXM18cvHh12uQ5vR4+Vai3VlSvVasnA7T1Yqa59zNMbpl/zwJp+/DXZ5+tf5Tc7+8xjssrzx0xvTGtX62nzKptqMaueV4v26p7c2Ko6H7nHm1jz0Wjx+Wat8WjzxovF5zusji6xZ7z/IzLwBlh7uY5vR/RKHSzVVSvVasnQL4I9WKmOfczTG6Zf9MB6qlaj16Zbi3px9fOG6fzcM8HRw/zHC886cWJoOq5eDtf+0sbWJZ+7ZXsfWJ69xE06Wq6j22Glto5X6tQ+5rWrdeVyTd/+dNIsxSFI93+fsLmVZbQkaFfrqYiNrSCXl8tKbYU9sB5otabzrgPLqpCWhOxqPZWxsRXm0nJZqZ2QB9ZjrdYy8uOP5/Ku1lMZG1thLi2XldoJeWBZrQdzaVfrqZCNrUDnl8tKfbr8wLJaD2d26ddDIRtbgc4tl5Xad+mBZbUez/ldradiNrYCnVsuK7Xv0gPLaj2gc7taT+VsbIXqXi4r1Xb+gWW1HlL3rtZTSRtbobqWy0odOvfAslqPatnrU8VaRny0bMsenwG4b/8P6HYD+Dm/rh8AAAAldEVYdGRhdGU6Y3JlYXRlADIwMjEtMTEtMTdUMTA6MzA6MjErMDE6MDCLbWbBAAAAJXRFWHRkYXRlOm1vZGlmeQAyMDIxLTExLTE3VDEwOjMwOjIxKzAxOjAw+jDefQAAABR0RVh0cGRmOlZlcnNpb24AUERGLTEuNSAFXAs5AAAAAElFTkSuQmCC" } }, "cell_type": "markdown", "id": "62e7623a", "metadata": {}, "source": [ "An example is given, where three pieces have to be placed inside the proposed grid.\n", "\"Layout\"" ] }, { "cell_type": "markdown", "id": "205274b9", "metadata": {}, "source": [ "To build a CSP (Constraint Satisfaction Problem) model, we need first to import the library PyCSP$^3$:" ] }, { "cell_type": "code", "execution_count": 1, "id": "876f91d0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", " \u001b[93mWarning: \u001b[0mUnknown option: -f\n", "\n" ] } ], "source": [ "from pycsp3 import *" ] }, { "cell_type": "markdown", "id": "7fc52723", "metadata": {}, "source": [ "Then, we need some data. Here, we decide to represent the grid and the pieces by two-dimensional matrices (0 being used to discard some cells)." ] }, { "cell_type": "code", "execution_count": 2, "id": "30961d5b", "metadata": {}, "outputs": [], "source": [ "grid = [\n", " [1,1,1,1], \n", " [1,1,1,1], \n", " [1,1,0,0], \n", " [1,0,0,0], \n", " [1,0,0,0], \n", " [1,0,0,0], \n", " [1,0,0,0]\n", "]\n", "shapes = [\n", " [[1,1], \n", " [1,0], \n", " [1,0], \n", " [1,0], \n", " [1,0]\n", " ],\n", " [[1,1], \n", " [1,1]\n", " ],\n", " [[1,1], \n", " [1,1]\n", " ]\n", "]" ] }, { "cell_type": "markdown", "id": "2f01695c", "metadata": {}, "source": [ "We define a few constants." ] }, { "cell_type": "code", "execution_count": 3, "id": "f7707828", "metadata": {}, "outputs": [], "source": [ "n = len(grid)\n", "m = len(grid[0])\n", "nShapes = len(shapes)" ] }, { "cell_type": "markdown", "id": "b6d9e7a6", "metadata": {}, "source": [ "We start our CSP model by introducing a first array $x$ of variables." ] }, { "cell_type": "code", "execution_count": 4, "id": "3b37d258", "metadata": {}, "outputs": [], "source": [ "# x[i][j] is the index of the shape occupying the cell at row i and column j of the grid (or -1 if the cell is free)\n", "x = VarArray(size=[n, m], dom=lambda i, j: {-1} if grid[i][j] == 0 else range(nShapes))" ] }, { "cell_type": "markdown", "id": "b249a616", "metadata": {}, "source": [ "We can display the structure of the array $x$, as well as the domain of the variables on the first and last row of $x$." ] }, { "cell_type": "code", "execution_count": 5, "id": "30040431", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Array x: [\n", " [x[0][0], x[0][1], x[0][2], x[0][3]]\n", " [x[1][0], x[1][1], x[1][2], x[1][3]]\n", " [x[2][0], x[2][1], x[2][2], x[2][3]]\n", " [x[3][0], x[3][1], x[3][2], x[3][3]]\n", " [x[4][0], x[4][1], x[4][2], x[4][3]]\n", " [x[5][0], x[5][1], x[5][2], x[5][3]]\n", " [x[6][0], x[6][1], x[6][2], x[6][3]]\n", "]\n", "Domains for first row of x: [0..2, 0..2, 0..2, 0..2]\n", "Domains for last row of x: [0..2, -1, -1, -1]\n" ] } ], "source": [ "print(\"Array x: \", x)\n", "print(\"Domains for first row of x: \", [x[0][j].dom for j in range(m)])\n", "print(\"Domains for last row of x: \", [x[-1][j].dom for j in range(m)])" ] }, { "cell_type": "markdown", "id": "0c3875df", "metadata": {}, "source": [ "For the second array we need to declare, we define first a function that returns for any shape k a list containing any cell c such that the top left cell of shape k could be placed on c while permitting the entire shape to be contained in the grid. " ] }, { "cell_type": "code", "execution_count": 6, "id": "e5ec790c", "metadata": {}, "outputs": [], "source": [ "def domain_y(k):\n", " shape, height, width = shapes[k], len(shapes[k]), len(shapes[k][0]) \n", " return [i * m + j for i in range(n - height + 1) for j in range(m - width + 1)\n", " if all(grid[i + gi][j + gj] == 1 or shape[gi][gj] == 0\n", " for gi in range(height) for gj in range(width))]" ] }, { "cell_type": "markdown", "id": "b6992ba9", "metadata": {}, "source": [ "For example, when we execute:" ] }, { "cell_type": "code", "execution_count": 7, "id": "a9dd1cdd", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 4, 8]\n" ] } ], "source": [ "print(domain_y(0))" ] }, { "cell_type": "markdown", "id": "5f848db9", "metadata": {}, "source": [ "we obtain a list with the indexes 0, 4 and 8, which correspond to the three highest cells of the first column of the grid. " ] }, { "cell_type": "markdown", "id": "8fdcbee1", "metadata": {}, "source": [ "The second array $y$ of variables is:" ] }, { "cell_type": "code", "execution_count": 8, "id": "525440c1", "metadata": {}, "outputs": [], "source": [ "# y[k] is the base cell index in the grid where we start putting the kth shape\n", "y = VarArray(size=nShapes, dom=domain_y)" ] }, { "cell_type": "markdown", "id": "32859da4", "metadata": {}, "source": [ "We can display the structure of the array $y$, as well as the domains of the variables of $y$." ] }, { "cell_type": "code", "execution_count": 9, "id": "9a218f9b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Array y: [y[0], y[1], y[2]]\n", "Domains of variables of y: [0 4 8, 0 1 2 4, 0 1 2 4]\n" ] } ], "source": [ "print(\"Array y: \", y)\n", "print(\"Domains of variables of y: \", [y[k].dom for k in range(nShapes)])" ] }, { "cell_type": "raw", "id": "668fcc9e", "metadata": {}, "source": [ "For linking variables of $x$ and $y$, we use the tables defined by the following function:" ] }, { "cell_type": "code", "execution_count": 10, "id": "13fba047", "metadata": {}, "outputs": [], "source": [ "def table(k):\n", " shape, height, width = shapes[k], len(shapes[k]), len(shapes[k][0])\n", " tbl = []\n", " for v in domain_y(k):\n", " i, j = v // m, v % m\n", " t = [(i + gi) * m + (j + gj) for gi in range(height) for gj in range(width)\n", " if shape[gi][gj] == 1]\n", " tbl.append((v,) + tuple(k if w in t else ANY for w in range(n * m)))\n", " return tbl" ] }, { "cell_type": "markdown", "id": "6cc27944", "metadata": {}, "source": [ "For example, when we execute:" ] }, { "cell_type": "code", "execution_count": 11, "id": "6ebc79f6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(0, 1, 1, *, *, 1, 1, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *)\n", "(1, *, 1, 1, *, *, 1, 1, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *)\n", "(2, *, *, 1, 1, *, *, 1, 1, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *)\n", "(4, *, *, *, *, 1, 1, *, *, 1, 1, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *, *)\n" ] } ], "source": [ "print(*table(1), sep=\"\\n\")" ] }, { "cell_type": "markdown", "id": "217dc6e8", "metadata": {}, "source": [ "we obtain four tuples. The first value of each tuple is the base cell where can be put the shape 1, and the other values indicate where the value 1 is consequently required in the grid." ] }, { "cell_type": "markdown", "id": "65f1ba1e", "metadata": {}, "source": [ "Concerning the constraints, we just need to post four constraints *Extension*. Technically, note that (y[k], x) is a shortcut for (y[k], *flatten(x))." ] }, { "cell_type": "code", "execution_count": 12, "id": "ef5a3020", "metadata": {}, "outputs": [], "source": [ "satisfy(\n", " # putting shapes in the grid\n", " (y[k], x) in table(k) for k in range(nShapes)\n", ");" ] }, { "cell_type": "markdown", "id": "9df2cc4e", "metadata": {}, "source": [ "We can display the internal representation of the posted constraints; this way, although a little bit technical, we can observe how these table constraints are formed." ] }, { "cell_type": "code", "execution_count": 13, "id": "a93c2153", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "extension(list:[y[0], x[0][0], x[0][1], x[0][2], x[0][3], x[1][0], x[1][1], x[1][2], x[1][3], x[2][0], x[2][1], x[2][2], x[2][3], x[3][0], x[3][1], x[3][2], x[3][3], x[4][0], x[4][1], x[4][2], x[4][3], x[5][0], x[5][1], x[5][2], x[5][3], x[6][0], x[6][1], x[6][2], x[6][3]], supports:(0,0,0,*,*,0,*,*,*,0,*,*,*,0,*,*,*,0,*,*,*,*,*,*,*,*,*,*,*)(4,*,*,*,*,0,0,*,*,0,*,*,*,0,*,*,*,0,*,*,*,0,*,*,*,*,*,*,*)(8,*,*,*,*,*,*,*,*,0,0,*,*,0,*,*,*,0,*,*,*,0,*,*,*,0,*,*,*))\n", "extension(list:[y[1], x[0][0], x[0][1], x[0][2], x[0][3], x[1][0], x[1][1], x[1][2], x[1][3], x[2][0], x[2][1], x[2][2], x[2][3], x[3][0], x[3][1], x[3][2], x[3][3], x[4][0], x[4][1], x[4][2], x[4][3], x[5][0], x[5][1], x[5][2], x[5][3], x[6][0], x[6][1], x[6][2], x[6][3]], supports:(0,1,1,*,*,1,1,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*)(1,*,1,1,*,*,1,1,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*)(2,*,*,1,1,*,*,1,1,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*)(4,*,*,*,*,1,1,*,*,1,1,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*))\n", "extension(list:[y[2], x[0][0], x[0][1], x[0][2], x[0][3], x[1][0], x[1][1], x[1][2], x[1][3], x[2][0], x[2][1], x[2][2], x[2][3], x[3][0], x[3][1], x[3][2], x[3][3], x[4][0], x[4][1], x[4][2], x[4][3], x[5][0], x[5][1], x[5][2], x[5][3], x[6][0], x[6][1], x[6][2], x[6][3]], supports:(0,2,2,*,*,2,2,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*)(1,*,2,2,*,*,2,2,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*)(2,*,*,2,2,*,*,2,2,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*)(4,*,*,*,*,2,2,*,*,2,2,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*))\n" ] } ], "source": [ "print(posted())" ] }, { "cell_type": "markdown", "id": "8a1e910f", "metadata": {}, "source": [ "Interestingly, by calling the function *solve()*, we can check that the problem is satisfiable (SAT). We can also display the found solution. Here, we call the function *values()* that collects the values assigned to a specified list of variables." ] }, { "cell_type": "code", "execution_count": 14, "id": "a3c82ffc", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[\n", " [1, 1, 2, 2]\n", " [1, 1, 2, 2]\n", " [0, 0, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", "]\n" ] } ], "source": [ "if solve() is SAT:\n", " print(values(x))" ] }, { "cell_type": "markdown", "id": "e180c42b", "metadata": {}, "source": [ "We can display the two possible solutions." ] }, { "cell_type": "code", "execution_count": 15, "id": "76e991aa", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Solution 0: [\n", " [1, 1, 2, 2]\n", " [1, 1, 2, 2]\n", " [0, 0, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", "]\n", "Solution 1: [\n", " [2, 2, 1, 1]\n", " [2, 2, 1, 1]\n", " [0, 0, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", " [0, -1, -1, -1]\n", "]\n" ] } ], "source": [ "if solve(sols=ALL) is SAT:\n", " for i in range(n_solutions()):\n", " print(f\"Solution {i}: {values(x, sol=i)}\")" ] }, { "cell_type": "markdown", "id": "26fabea1", "metadata": {}, "source": [ "Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line)." ] }, { "cell_type": "raw", "id": "11ac7858", "metadata": { "raw_mimetype": "text/x-python" }, "source": [ "from pycsp3 import *\n", "\n", "grid, shapes = data\n", "n, m, nShapes = len(grid), len(grid[0]), len(shapes)\n", "\n", "\n", "def domain_y(k):\n", " shape, height, width = shapes[k], len(shapes[k]), len(shapes[k][0])\n", " return [i * m + j for i in range(n - height + 1) for j in range(m - width + 1) if\n", " all(grid[i + gi][j + gj] == 1 or shape[gi][gj] == 0 for gi in range(height) for gj in range(width))]\n", "\n", "\n", "def table(k):\n", " shape, height, width = shapes[k], len(shapes[k]), len(shapes[k][0])\n", " tbl = []\n", " for v in domain_y(k):\n", " i, j = v // m, v % m\n", " t = [(i + gi) * m + (j + gj) for gi in range(height) for gj in range(width) if shape[gi][gj] == 1]\n", " tbl.append((v,) + tuple(k if w in t else ANY for w in range(n * m)))\n", " return tbl\n", "\n", "\n", "# x[i][j] is the index of the shape occupying the cell at row i and column j (or -1 if the cell is free)\n", "x = VarArray(size=[n, m], dom=lambda i, j: {-1} if grid[i][j] == 0 else range(nShapes))\n", "\n", "# y[k] is the (index of the) base cell in the grid where we start putting the kth shape\n", "y = VarArray(size=nShapes, dom=domain_y)\n", "\n", "satisfy(\n", " # putting shapes in the grid\n", " (y[k], x) in table(k) for k in range(nShapes)\n", ")" ] } ], "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.7.12" } }, "nbformat": 4, "nbformat_minor": 5 }