Solving the 15-puzzle Curtis Bright, Maplesoft TUZOV3RLVWI8b2I8Uj1NRExDZE5GWkVsOj5bPEo6YFU7YUxoYz5BWUxDVEpjRFhvWHV1WGlXdXJnZDpHQk51V0pPRnVnU0Q/VnRBVlpJZzxbRkBbSWhfVGRFaD9xZklXR1U7dWhldV5Pc3RrR1ddU2U9WWRzZlBxaTxfVXVJQ1ZPdEdXdEZFZEE9ZU9XZlJPdnk/R0RRdndfRkl5YlVhQ2ZrRlJrc2FZUmxReExPZXZtREtDY29TRHU/Uj49Q19LRjw9R0tDRk4/Y0JDZj5dYkpNRlxcY0lMS3dJd0l4QWl2X2l2SVU+XWZNX1l0YXhjVUNbb2R2Y1M+XVJ0T3NMQ2dnW2JUbVl0ZWhTSWhOS2hUWUhZYVl1aWlLV0VDVXVOX1JnbWhnZ1NVQ2ZQV2lPaVZqZXRISXlZeVd5V0VzR3hFeWdtaXZYR3lqSXY9T2ROX3lgZ0ltYXhXT2ROc3JEQ0c8RUREP1Q+T0ZOQ2ZCY1JiS1JLSzs6Ojo6X2JKXWJcXE4+TFJiTFJLQjw6OkZbW0BbP2tCYkpLY0pdWj48Oko8O0taW15cXFtAO0Q+Ojo/PF5KY0Y+T0ZOQ05EOjpqSjo/PDo6Ojo6Wk5BZz9QaXZIbUhvYGBhaTs/b1lxaVl4X2hwW1h4eEBJdz9Zck1Baz9QZVZ4Y1R4XkZXaDxYW292aXJ4YXVec2dRa11YcD9ZXFxbcHhOeWA8Z251dmJiTmJPaWtlWXNdUHdXTlxcUklveElbT0F3Tk5nblFiX3dbQ2BqXFxeZHVubTxZXk95YVtQbHRoWj0/X3RHbkR2ZmZZXlFOb3NJZmk+ZWFQYkNmeGx2W2p5Zkh2b2hYZHdGbVlxbWhYXW5PYGFedHB4bkpXdFV4YjxnZ2RhXVtwcGJgZEJxYj9QXFxkUXZecHNaYGRRUGpPP29xT2I/b2lEZlxcTD9vc1lydm9sXFxHZ3BXbXZJbEpXbUVmXFxwQWtRXmJiYHRzcGhzaWhWT29LX2pUPnNjXmReTmJ3dnhjbmp0Z2JpXmRWbmE/UXFUQWZ3R25hUV9paHVjXmRoT1tublpvUGpFZmB1aGlEeFZrUmhbVGZrST9FR05ReTw7dEZFWVVXVGJHd25LaVVBWUtpZ3A7Rk51U3ZNY0A9Z1ZhUjtndEBTeXR3V1Y7RGNLUm9hUmI/ZXZNY0E9Z0xXdWZbYmRVWERjVFRdZ25RU2M/VndXRk51Rz5PU3RPRENpQ1E/VT5PU2k/SEJldlpReFg/VGlfWUxnREQ/RzxleDo9Z3Jxd3FfcnNTVFhTck5ddFpxZVZrQ0ddRFtPdlFLR3BXRGJ3c0tzSXNbVXk/VkQ/VHVzdWdZRk5DZlxcU1dCdWk+T1VJYVNfdVRWV0REP1Q+T0VJO1RLU0NPS2k/VWJNS0duYUQ9Q2ZcXHNEZGtzQU9EQmNIRkNmVFtTbGNiaDtGW092UEtHTHlmYE9Cd2N4TF9IXk9YXFxbWXd1WElpVFhZV0pjaFg9WEpLZzpfYkRPVWI/VVlTd0ZfeENJdk5ZU2xLUmc7SWJpd011R19jRkVleWZbdVddVjxlcmZbVG53Y29tUmtxeE9fR0xFdW9pdlhfRWhlVk5dYklpaUpLR2BFZlxcZ1lta2JxO3VHS1dgX2lQQ2c6aXVdW1Q+UVI/WXlgXUNpRUJYa3V3X2lcXFl1OldmYmdFW09GUEtHWHlkRWdyanVHaWNoPF91cUNHRnNIeGdjRHloS2VDY2VoO0NmQmNKPEtEPjtLU0JaPGNcXDo6Ojo6OjpiWD9ERD88Q05EdXBCZFJiQj86OnJaW0RbPzs6Wjw7OmBLPEVMRDo6Uj46WkRBXk5GbkI6OmJcXDo6R1JiS1JLOjpeanRZeFFAaG9IbV5RcFRZYHleeXV5YUBvZ2ZQb3BxeGdZZV9GZFVwdl1GbmBoa0pPXlxcZl1eaGtKV3M9T25NP3RcXEFlY3h3bGhuUlhxdVhxX3Ftc0l4YVhbX0ZfSGh2WEhpeXF5d1BsTlZodl9pRj9fPEc8Tj49Pzo6Ojo6Ok5kZk5iS05LRDw6OkVFPk9GTjo6ZkI6Wj08OjpEPjpSQDo6Wks6OmRGOjpiXFw6Ojo6anRpd3FZa01IU3B0blF0S0ldanRheXNFWFhYdWtUbGNpc11BUz9QbWlsb0hscGZxUkVoU0BUT055VU9NUVk9TGRVb2tlWXNdUGNQc1tpdG89VGFQakRkeHJVUGdgdWtEclNQd1g9b3NZcndJdVtxWEF1b1BUbUZsVGJoWFVAS29RVXZkYmNAaDxndGxhXFw7TmRXVltPUHBgSF9xZl9wRl1oQGRjWWBrT2JnZ2lMcWVMSW5GZ3FIb3ZdWFxcZFBwS0ddc1BaVGZ0X0BkU1dnVEZoTVFmTUh2RGZsdU51S05vP2F1TWdyQ1B0RXlaSHBzUHZjXVBcXGRGWmRgdFpoYFlHdkJQd0Y/b2ZJZmZIXFxxZl9wQmZbVFthV1Y/bHk8UEhxV1lQd2VwWGpFWXlsTltQTDxQT0RhTDthbTx1Sjxlc1lsdm1gdGlsdGZxUHNZVl90UGdsUFM8cUpVd2RkbVlYTGRoV3lRTU5sT0ppalhdb2VoS1B0dl1RTGRJcVtUdU9sbmtxTj1tTGRUWF5UVUpMV1lQUj9MbWl0a049b15IWT1wcURZVXdZd2F0dlFpc0VUcE9xTj1pTGR0dExMUm94cURZb1ZwVkQ/ZEJWcHZOX0xHblhPc3BObFNQeFBhdUZIZWJQWkJfalRpZmBgcWZRXmg+dldRdnJoakRva0dIXmVwYmJAbT9QX3VGc2BedEh4cGNPcFFJaD9YdWteamRfaFV4a0pfamRAb0JGblh3dlt3bGZvY0h3Zj5Qa2VxXlhGblxcdlxcZFBjXFxOYndQYUx3Xm1BZEdWa00/b3I/aVxcXmRmUGJPYXU9R15OWXdnYGlDb3ZIeXRRUWldeHFReHBYZ25TRlpJX2pEWGRiUGU+QFtveGtMb3VYcGNmeGpEeGthTmI/R19OR3hvPl1vRltNYW5bSFtPYGU6bmtmZ2NzR2lnUW5yV3dERm5CZmBMRm5MZ3djdmVJZnBrWVo9eVxcZGdhbWFcXE9wYz5QXk5BYUhJbnBeb0FQY2hGeDxpcTpoXl5AZEtnY0ZYXFxkeHhpP3BtdltvWHNuVmRQRm9WWW9tTm9YWF9YdnJ1SW5cXF92Q0BkPlBdRWFhTnFqb0FkW3FmWlByRGZ0Wml5b1dyeU9oUkBkPlBbaV5kW2ljXUdtPl5hdU9bZF5kXT9uQmZiYlJXd2lmVUh2SWdNXUhpeWJcXFtEW0xzcUhUc3FQZHBRQmR2VUFvQDxMPF88UD5dOjo6Ojo6Ojo6OjpQbEpMa0pdOj9MX1hVPlBOTmJcXDo6Xmw7P188Rzw6OmM6OkI9P1Q+OjpCPDpaX2NcXDo6Uks6OkE+OkJPc2JKVXN2UXhlYXVCaWNfW3VFaUltdUY/X2dkVVh2eWN5RUdDRVhmc3hGeXRZdVlnX0Y/YWdiR1djW2RCP1tfQGRZXm5KeGhpcXVncG9fX2tWQWF4eXZJVnN3VmBXcGNPYG5SaHZYSHlcXFlzeUhfQ0dobnhcXGRHaXc/d1xcRnFkd3ZSQGVjbmtPaXBGUXhxSGRDT2N4V3RYeF5wd3FNT2xcXEFlR1dtSk5rSktEWjw7Ojo6OmZePlBeTmpcXFI8Wks6OkpDOj9bPkBEQjw6OkY7akJiSkRuQkJbOjpeSko+UkJAREQ+Ojo/PF5KOjo6Ojo6XFx0QmRqdF1xU3BPeXlyTVh4P1VwSWlubGRxc11NUUBUUXROc2hRal1YcEBZVFRuSlVNdVRUZlRTQ21QUG1XQkxSV3VVWGR2eFF1bVh1YUxSZ2V1b1B5dGB0cGlvRXRuPFhLT113U1FRQXhUUXlLSVVWTExvO3VWUHR2TUh0RWRQWV1VV1xcVHhpdT10TVVReVxcXFxUVG1tRFFxbjxRVmx3V0RvalBST0l4blBzQ2FZbkxSd3BUYW1KaFxcVGd0U1tJbGRpakpFcVBkVE5pTndJb1ZcXFJjWXZecW1FcUxKPW9zaXdjRW8+VXhBWHltWHJqeW5oaXVEZHRmWFBjUFdmaU1bQFU/UFNHPUtWcFVecFNreHZJVHhTXUpBbHBiaWpkRFFAaWxxRVdnQFRjeXNReXlXaHlQRVBOQFRTbGpEUXlucE9cXD1ucGhYYVxcVF1xc15wUVRpdUZlVk5NUl9ATWREUUtNU1dwVV89eFxcXFxUQ2FLO0l5XFxweWJ1cGtQV1dkTWZUakNkcGNgUztZdVBJa0pVVW9tTlhYVGJATT5QT2NlUnd5U0NkbGV1c2hlVmRRb0RIbj5QVUlBUj9YUVt0a0M9b2BlbUNodk5MT1pAVENJb3Fld3NcXFRyWFlmRHBFZGxkbVR1VVZMdUpQSXJIYWxhTnZcXD9xPV9dUD9vZ05hTWh5c293cHBlUVBnP2BtY3ZlSXdlUG9zPWdaZmZkSXBkVV5nZV5ka3FgbEFmUVddTnZrPkhtY29zWnhmY0liUVddZj93RlF5Tk5ndGZbcFddaW5qT3FaY1lpZmZqPmhhYGlbUT9vTEh3TElaRWZsU3hfYl5fUWFtPkFoOz5dW0BkR3B0PGdoPGBkamlcXFVIcVVucWteX1pYXXRAZE9md1V5cExHcj9QbVdAZUlmdGpYYGNYalJHY2dOZ1B3b0ZWd2R2b05xbmJfbVQ+eE9vZVJIb2JAdDxnbEZRaUhUSWN4dHN4QU1kZ3l4R11UPlNIX0lZQ09IX09ITW11X1V1cFFZUHFFWD1nRE9IRz9Xd1t0ZWt1O2l3RD9nSk1ST3l1PGtTdWlYakVZST1nd3NoZ1dkVVVzW2diZF9ZOkVGcmllXXFVRGN0T1FHTz9GPGV0aWNIQl9mcFNWTEtnTW9oP29pUXdUc3VzaDt5ZFlJPGVyYVt0YFFTPnNnR0NmQD9GTk13XFxrY0pleXVzd2BbdFJbYmQ9SFs9dENhZTw9aGFvVVhtZG5fVEddYnVPc1VJZ21TWVhFWFpRR2k9eWFBVFVvRjx5dHFzY3FRWXJbQ3FhdmpxYl1lVWxTVFhLV0RZSGBpeEplRE8/d2RJWG1BWG1jdlVTVUtbeUBTczpvZ2xRd1h1Qk5pdWV5VDxraXdlRm9RWGJPZU9xQjtxRFF3cnJlZFF1dEVvR1lnZERzaFRBRm1RWGJfdU11R2NRdT5TWT9ddFpvdltvUnhxQnVnc0V1dzxvSTtBRGFhSU5VYl9ldlddSXFRRGplcmBxdnFvRUBXSWlxRVphU3NBc1lRQlZ1Y049clhncnZTVFhVY051UmllVmthVVhBaWhpdk9LSXFrZ2lNVGJbR2tzY1xcaWRmQ1hZWXNFQ3lnWUVZV1Z3cUY/P2hBX0hZcVJvO1VbX1lVY1RpUXZVQWdCY1JiPj9kUmI6Ojo6Ojo6OlpjSVtbQFs/a0JiO1xcOko8OzpfQzxFREQ6Ok4+OkpEPz86Ol48OlpGOjo6XFw6OlJTOmZCOjpSVlFSQz9jblVkUE9Sd0dZbXF2Uk1oc1F3ZXdnUFdZYGlpTktoZlVzbHVzdkV4X3l1UXdGRWtSaF1neEVmTl9mUmdlPk9VeFFSeHlUbEdVaFlkX3Fla0V1TF1zV2l1V1FYSWF5cll0P1dHUU92UkV4Xl9GP2FneEVmQmNSYjpMQjo6OjpKP2BOPEVMRDo9U1xcW0RbPztSPk8+Om06WkNCPFI+OjpOQDpEW0taXFw6OmpsOlJDQz5QPjo6T0BaRDw6Ojo6OlpPYHZrcWZ0YXlJTmh4QHVuSXI/SXledmxjaXNdQWo/UG1pbm9Ibm15cWxheFxcSXZjVXdndVdpdEZndWhnSV5qZE91U0BqT0heTkFiPlB5ZVhnVU51UF9nVE9fVWhnZUluSld4QVxcQ1dhX29lYlddZEBkR09hTWBpYGBfV0dgPz9veFhbT3BvS2doVVFnRXF0R1d2dG5cXGRmck1xdERhc1ludm1IY0VpZ3VBXk5XbEhhZ2hfY3E+Y0tOb1FRYl9RZ05HX05PeXZJX21JbkR5XW5ZZWJgX0lXdWNWcEVxcHc/XFxkSGVhT19FSGxTYXE9Vm5CZnRVR25Eb1tsZ1xcZ1dleU9wZkhkZXltaHlsYnBzPlBjVz9ub0hkYFF5bEFvb3Fwa1hbT0FxbUZbSmduQGZvc1F1eUZkPlB3XUBkU0hfX1h4P094QWljQVlyUHhhaWlrSkd1ZVhwQ2F3cEZ5XVdkX29lYHdyYVZsTVh0U0FuPlB1ZFhgVVBdS2l0S2drSmdpUU5nT3lrR2ZpVGFbSndePmdoZV50bVZfc3hhaEdhdW5hWT5vSmdrdFZwX3lpR0BkPlBfblleT2drdFFxXnZydVB3bU54QHZdY0lsSldwVXluTD9wVHZjeWZdV2hfcHB0Z3hcXDxnYGhhY11Zbz93ZHNfalRJeTpwYFxcRm5keWNjUHd5XmlrT2xWV114Zmd1aGdJdmRVXndgXnRFcXRgT3NDZnB1V3VUYGhrWGtNcHhSaGpEb2ZBeVtodndVP3dwTmBbUG1neHFdXlxcW0Bbb1FfPGdvYXdySXZvaHg9S1JvW3VsV2VvU2U+T0ZOQWc/T2d0YUNbT1JZYXJdW0Rbb1JpW1RobVh2Z3hWa3RCXWJkcWVhS1JTR0dZY3hGRVlobVhWP1RHbUhiUWRhS1JLS1d2T1JfcWRxbVdEcVlXT2NWPWdKXUlLS1dGS1JHP1c/cUZbb3haW1RRd2NyP0RkXWQ8ZUh5SXlYVUdCPWd4SUNPdXk+dUZbP0NvUUlnVVd0YXZqcVlVPUVzUWNHVXhKRVRGXWNNS1dGT1JfdUVVY1N1W2RzbXR3PVJpdVVbW3RIaWVjYVhTbUZbb3JoW3RCc3VadVJiZ1V0U3RaaXlvbWVWa0ZOWWdISUdOeVhoPWZpRUJgW3RId3h5RUM/PWdodXdWc2R2X2d2V2dtP1k8ZXhBPWdUeVhUWUREP1Q9X2NpVWZsaVdOXWJcXFs8ZkJCTjo6Ojo6Ojo6Ojo6OjpfO1pMUj5iQjo6ZkY8P1JDXjxQPjo6T0BaRD9bPz8/ZEI6OmM+Ols6TDtSVWdiVEVGX0N3dkdZbXFiSl1iXFxAVT5QbExBbHRAbV51dnZVeGd5eEBtV2JoU3dlV3BYTGRZdkF5a0ZMTEtwc2xobUpVT15wWVBETGNhTllwUXdNdUg9T0tGcj0/X0tGXk5EPExeSmNCQ25CRktDWGB5eTppQltMeFBIVFxcdFc6PEo6PGpeUF4+b288P2Y8NDxcIlx7XH0=LSUrQU5OT1RBVElPTkc2Jy0lKUJPVU5EU19YRzYjJCIiISEiIi0lKUJPVU5EU19ZR0YnLSUtQk9VTkRTX1dJRFRIRzYjJCIlXVJGKi0lLkJPVU5EU19IRUlHSFRHRi8tJSlDSElMRFJFTkc2Ig== The 15-puzzle is a classic "sliding tile" puzzle. It consists of a LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbW5HRiQ2JlEiNEYnLyUlc2l6ZUdRIzE2RicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictSSNtb0dGJDYvUSgmdGltZXM7RidGL0YyRjUvJSZmZW5jZUdGNC8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSwwLjIyMjIyMjJlbUYnLyUncnNwYWNlR0ZMRitGMkY1 grid containing tiles numbered 1 through 15 along with one missing tile. The objective of the puzzle is to arrange the tiles so that they are in ascending order when read from left to right and top to bottom. The only moves allowed are those that slide a tile adjacent to the blank space into the blank space. It is known that every valid position can be solved in at most 80 moves. It's possible to solve this puzzle without any knowledge of search algorithms at all. To do this we encode the rules of the puzzle as constraints in mathematical logic and use Maple's built-in efficient SAT solver to find a solution. A SAT solver takes as input a formula in Boolean logic and returns an assignment to the variables which makes the formula true (if one exists). See the Satisfy command for more information.

We'll use the Boolean variables LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2J1EiU0YnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSShtZmVuY2VkR0YkNigtRiM2Ky1GLDYnUSJpRidGL0YyRjVGOC1JI21vR0YkNi9RIixGJ0YvRjUvRjlRJ25vcm1hbEYnLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRiw2J1EiakYnRi9GMkY1RjhGQy1GLDYnUSJuRidGL0YyRjVGOEZDLUYsNidRInRGJ0YvRjJGNUY4RjVGR0YvRjVGRy8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJy1GLDYjUSFGJ0Y1Rkc= to denote that the square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZELUYxNiNRIUYnRjpGRA== contains tile LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EibkYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= after LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= moves. Here LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUkjbW5HRiQ2JlEiMUYnLyUlc2l6ZUdRIzE2RicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictSSNtb0dGJDYvUSYmbGVxO0YnRi9GMkY1LyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JI21pR0YkNidRImlGJ0YvLyUnaXRhbGljR1EldHJ1ZUYnRjIvRjZRJ2l0YWxpY0YnLUY5Ni9RIixGJ0YvRjJGNUY8L0Y/RlVGQEZCRkRGRkZIL0ZLUSYwLjBlbUYnL0ZOUSwwLjMzMzMzMzNlbUYnLUZQNidRImpGJ0YvRlNGMkZWRjgtRiw2JlEiNEYnRi9GMkY1RjJGNQ==, LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbW5HRiQ2JlEiMUYnLyUlc2l6ZUdRIzE2RicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictSSNtb0dGJDYvUSYmbGVxO0YnRi9GMkY1LyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JI21pR0YkNidRIm5GJ0YvLyUnaXRhbGljR1EldHJ1ZUYnRjIvRjZRJ2l0YWxpY0YnRjgtRiw2JkYxRi9GMkY1RjJGNQ== (we let 16 denote the blank tile) and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbW5HRiQ2JlEiMEYnLyUlc2l6ZUdRIzE2RicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictSSNtb0dGJDYvUSYmbGVxO0YnRi9GMkY1LyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JI21pR0YkNidRInRGJ0YvLyUnaXRhbGljR1EldHJ1ZUYnRjIvRjZRJ2l0YWxpY0YnRjgtRiw2JlEjODBGJ0YvRjJGNUYyRjU= since each instance requires at most LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2J1EiTUYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYvUSJ+RidGL0Y1L0Y5USdub3JtYWxGJy8lJmZlbmNlR0Y3LyUqc2VwYXJhdG9yR0Y3LyUpc3RyZXRjaHlHRjcvJSpzeW1tZXRyaWNHRjcvJShsYXJnZW9wR0Y3LyUubW92YWJsZWxpbWl0c0dGNy8lJ2FjY2VudEdGNy8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlFGOy1GPDYvUSI9RidGL0Y1Rj9GQUZDRkVGR0ZJRktGTS9GUFEsMC4yNzc3Nzc4ZW1GJy9GU0ZYRjstSSNtbkdGJDYmUSM4MEYnRi9GNUY/RjVGPw== moves to solve. We'll also use a function to compute squares which are adjacent to a given square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA==. # Returns the set of squares adjacent to square (i, j) adjacent := proc(i, j) local x, y; return {seq([x, j], x=max(1, i-1)..min(4, i+1))} union {seq([i, y], y=max(1, j-1)..min(4, j+1))} minus {[i, j]}; end proc:

The board does not permit two tiles to occupy the same square at the same time. These constraints are of the form LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbW9HRiQ2L1EmJm5vdDtGJy8lJXNpemVHUSMxNkYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjQvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNC8lKnN5bW1ldHJpY0dGNC8lKGxhcmdlb3BHRjQvJS5tb3ZhYmxlbGltaXRzR0Y0LyUnYWNjZW50R0Y0LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMjc3Nzc3OGVtRictSSNtaUdGJDYnUSJTRidGLy8lJ2l0YWxpY0dRJXRydWVGJ0YyL0Y2USdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2KC1GIzYsLUZNNidRImlGJ0YvRlBGMkZTLUYsNi9RIixGJ0YvRjJGNUY4L0Y7RlJGPEY+RkBGQkZERkYvRkpRLDAuMzMzMzMzM2VtRictRk02J1EiakYnRi9GUEYyRlNGZ24tRk02J1EibkYnRi9GUEYyRlNGZ24tRk02J1EidEYnRi9GUEYyRlNGL0YyRjVGL0YyRjUvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRictRiw2L1ElJm9yO0YnRi9GMkY1RjhGOi9GPUZSRj5GQEZCRkQvRkdRLDAuMjIyMjIyMmVtRicvRkpGYXAtRiw2L1EifkYnRi9GMkY1RjhGOkY8Rj5GQEZCRkRGRi9GSkZIRitGTC1GVjYoLUYjNixGWkZnbkZdb0Znbi1GTTYnUSJtRidGL0ZQRjJGU0ZnbkZjb0YvRjJGNUYvRjJGNUZmb0Zpb0YvRjJGNQ== for each valid tile numbers LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2J1EibkYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYvUSUmbmU7RidGL0Y1L0Y5USdub3JtYWxGJy8lJmZlbmNlR0Y3LyUqc2VwYXJhdG9yR0Y3LyUpc3RyZXRjaHlHRjcvJSpzeW1tZXRyaWNHRjcvJShsYXJnZW9wR0Y3LyUubW92YWJsZWxpbWl0c0dGNy8lJ2FjY2VudEdGNy8lJ2xzcGFjZUdRLDAuMjc3Nzc3OGVtRicvJSdyc3BhY2VHRlEtRiw2J1EibUYnRi9GMkY1RjhGNUY/, valid indices LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EiaUYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EiakYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=, and valid timestep LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=. We define the function LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1E0bm9TcXVhcmVIYXNUd29UaWxlc0YnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= to generate these constraints up to timestep LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EiTUYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=. # Returns a set of constraints specifying no two tiles occupy the same place at the same time (up to timestep M) noSquareHasTwoTiles := proc(M) local t, i, j, n, m; return seq(seq(seq(seq(seq(&not(S[i, j, n, t]) &or &not(S[i, j, m, t]), m=n+1..16), n=1..16), j=1..4), i=1..4), t=0..M); end proc:

Next we need to generate constraints which tell the SAT solver how the state of the board can change from time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGL0Y1L0Y5USdub3JtYWxGJw== to time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYvUSIrRidGL0Y1L0Y5USdub3JtYWxGJy8lJmZlbmNlR0Y3LyUqc2VwYXJhdG9yR0Y3LyUpc3RyZXRjaHlHRjcvJSpzeW1tZXRyaWNHRjcvJShsYXJnZW9wR0Y3LyUubW92YWJsZWxpbWl0c0dGNy8lJ2FjY2VudEdGNy8lJ2xzcGFjZUdRLDAuMjIyMjIyMmVtRicvJSdyc3BhY2VHRlEtSSNtbkdGJDYmUSIxRidGL0Y1Rj9GL0Y1Rj8=. There are two cases to consider, depending on if a square (or an adjacent square) contains the blank tile.

The easier case is when a square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== and none of the squares adjacent to that square are blank. In that case, the rules of the puzzle imply that the tile in square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== does not change. We define the function LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EuZG9lc05vdENoYW5nZUYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= that generates a constraint that says that the tile in square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== does not change at time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGL0Y1L0Y5USdub3JtYWxGJw==. These constraints are of the form LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkobWZlbmNlZEdGJDYmLUYjNiotSSNtaUdGJDYnUSJTRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GLDYoLUYjNiwtRjE2J1EiaUYnRjRGN0Y6Rj0tSSNtb0dGJDYvUSIsRidGNEY6L0Y+USdub3JtYWxGJy8lJmZlbmNlR0Y8LyUqc2VwYXJhdG9yR0Y5LyUpc3RyZXRjaHlHRjwvJSpzeW1tZXRyaWNHRjwvJShsYXJnZW9wR0Y8LyUubW92YWJsZWxpbWl0c0dGPC8lJ2FjY2VudEdGPC8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHUSwwLjMzMzMzMzNlbUYnLUYxNidRImpGJ0Y0RjdGOkY9RkctSSNtbkdGJDYmUSIxRidGNEY6RktGRy1GMTYnUSJ0RidGNEY3RjpGPUY0RjpGS0Y0RjpGSy8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJy1GSDYvUSYmaWZmO0YnRjRGOkZLRk0vRlBGPC9GUkY5RlNGVUZXRlkvRmZuUSwwLjI3Nzc3NzhlbUYnL0ZpbkZhcEYwLUYsNigtRiM2LkZERkdGW29GR0Zeb0ZHRmJvLUZINi9RIitGJ0Y0RjpGS0ZNRl5wRlFGU0ZVRldGWS9GZm5RLDAuMjIyMjIyMmVtRicvRmluRltxRl5vRjRGOkZLRjRGOkZLRmVvRmhvRjRGOkZLRjRGOkZLLUZINi9RJiZhbmQ7RidGNEY6RktGTUZecEZfcEZTRlVGV0ZZRmpwRlxxLUZINi9RJyZzZG90O0YnRjRGOkZLRk1GXnBGUUZTRlVGV0ZZRmVuL0ZpbkZnbkZgcUZgcUZdcS1GLDYmLUYjNipGMC1GLDYoLUYjNixGREZHRltvRkctRl9vNiZGNkY0RjpGS0ZHRmJvRjRGOkZLRjRGOkZLRmVvRmhvRltwRjAtRiw2KC1GIzYuRkRGR0Zbb0ZHRlxyRkdGYm9GZ3BGXm9GNEY6RktGNEY6RktGZW9GaG9GNEY6RktGNEY6RkstRjE2I1EhRidGNEY6Rks=. For convenience, we also define the following functions: * LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1Ewbm90RXF1YWxUb0JsYW5rRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJ0Y1L0Y5USdub3JtYWxGJw== that says square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== does not contain the blank tile at time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSdtc3BhY2VHRiQ2Ji8lJ2hlaWdodEdRJjAuMGV4RicvJSZ3aWR0aEdRJjAuMGVtRicvJSZkZXB0aEdGQC8lKmxpbmVicmVha0dRJWF1dG9GJy1GLDYjUSFGJ0Y1L0Y5USdub3JtYWxGJw== * LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1E6bm90RXF1YWxPckFkamFjZW50VG9CbGFua0YnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= that says square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== (or any adjacent squares) do not contain the blank tile at time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= * LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1Esc3dhcFNxdWFyZXNGJy8lJXNpemVHUSMxNkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjUvRjlRJ25vcm1hbEYn that says the tile at square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== swaps with the tile at square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJrRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EibEYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== at time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= The static transition constraints are of the form LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2J1E6bm90RXF1YWxPckFkamFjZW50VG9CbGFua0YnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSShtZmVuY2VkR0YkNiYtRiM2Ki1GLDYnUSJpRidGL0YyRjVGOC1JI21vR0YkNi9RIixGJ0YvRjUvRjlRJ25vcm1hbEYnLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRiw2J1EiakYnRi9GMkY1RjhGQy1GLDYnUSJ0RidGL0YyRjVGOEYvRjVGR0YvRjVGRy1GRDYvUSomSW1wbGllcztGJ0YvRjVGR0ZJL0ZMRjcvRk5GNEZPRlFGU0ZVL0ZYUSwwLjI3Nzc3NzhlbUYnL0ZlbkZjby1GLDYnUS5kb2VzTm90Q2hhbmdlRidGL0YyRjVGOEY7Ri9GNUZH for all squares LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== and timesteps LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=. # Returns a constraint that states square (i, j) does not contain the blank tile at time t notEqualToBlank := (i, j, t) -> &not(S[i, j, 16, t]): # Returns a constraint that states square (i, j) is not adjacent or equal to blank at time t notEqualOrAdjacentToBlank := proc(i, j, t) local x; return &and(notEqualToBlank(i, j, t), seq(notEqualToBlank(x[1], x[2], t), x in adjacent(i, j))); end proc: # Returns a constraint that states the squares at (i, j) and (k, l) swap positions at time t swapSquares := proc(i, j, k, l, t) local n; return &and(seq(&iff(S[i, j, n, t], S[k, l, n, t+1]), n=1..16)); end proc: # Returns a constraint that states square (i, j) does not change at time t doesNotChange := proc(i, j, t) return swapSquares(i, j, i, j, t); end proc: # Returns static transition constraints up to timestep M staticTransitionConstraints := proc(M) local t, j, i; return seq(seq(seq(notEqualOrAdjacentToBlank(i, j, t) &implies doesNotChange(i, j, t), i=1..4), j=1..4), t=0..M-1); end proc:

The harder transition case is when a square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== contains the blank tile. In that case, we need to encode the fact that the blank tile will switch positions with exactly one of the squares adjacent to square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA==. If the blank tile on square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkobWZlbmNlZEdGJDYmLUYjNigtSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GNEY6RkRGNEY6RkRGNEY6RkQ= switches positions with the square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2J1EiWEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYvUSJ+RidGL0Y1L0Y5USdub3JtYWxGJy8lJmZlbmNlR0Y3LyUqc2VwYXJhdG9yR0Y3LyUpc3RyZXRjaHlHRjcvJSpzeW1tZXRyaWNHRjcvJShsYXJnZW9wR0Y3LyUubW92YWJsZWxpbWl0c0dGNy8lJ2FjY2VudEdGNy8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlFGOy1GPDYvUSI9RidGL0Y1Rj9GQUZDRkVGR0ZJRktGTS9GUFEsMC4yNzc3Nzc4ZW1GJy9GU0ZYLUkobWZlbmNlZEdGJDYmLUYjNigtSSVtc3ViR0YkNiYtRiw2J1EieEYnRi9GMkY1RjgtRiM2Jy1JI21uR0YkNiZRIjFGJ0YvRjVGP0YvRjJGNUY4LyUvc3Vic2NyaXB0c2hpZnRHUSIwRicvSSttc2VtYW50aWNzR0YkUSdhdG9taWNGJy1GPDYvUSIsRidGL0Y1Rj9GQS9GREY0RkVGR0ZJRktGTUZPL0ZTUSwwLjMzMzMzMzNlbUYnLUZqbjYmRlxvLUYjNictRmJvNiZRIjJGJ0YvRjVGP0YvRjJGNUY4RmVvRmhvRi9GNUY/Ri9GNUY/Ri9GNUY/ at time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGL0Y1L0Y5USdub3JtYWxGJw== this can be encoded as the clause LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2J1Esc3dhcFNxdWFyZXNGJy8lJXNpemVHUSMxNkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkobWZlbmNlZEdGJDYmLUYjNi4tSSVtc3ViR0YkNiYtRiw2J1EieEYnRi9GMkY1RjgtRiM2Jy1JI21uR0YkNiZRIjFGJ0YvRjUvRjlRJ25vcm1hbEYnRi9GMkY1RjgvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJy9JK21zZW1hbnRpY3NHRiRRJ2F0b21pY0YnLUkjbW9HRiQ2L1EiLEYnRi9GNUZMLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGNy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRkE2JkZDLUYjNictRkk2JlEiMkYnRi9GNUZMRi9GMkY1RjhGTkZRRlQtRiw2J1EiaUYnRi9GMkY1RjhGVC1GLDYnUSJqRidGL0YyRjVGOEZULUYsNidRInRGJ0YvRjJGNUY4Ri9GNUZMRi9GNUZMRi9GNUZM. We also need to enforce that all squares adjacent to LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== other than LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkobWZlbmNlZEdGJDYmLUYjNigtSSVtc3ViR0YkNiYtSSNtaUdGJDYnUSJ4RicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYnLUkjbW5HRiQ2JlEiMUYnRjdGPS9GQVEnbm9ybWFsRidGN0Y6Rj1GQC8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnL0krbXNlbWFudGljc0dGJFEnYXRvbWljRictSSNtb0dGJDYvUSIsRidGN0Y9RkkvJSZmZW5jZUdGPy8lKnNlcGFyYXRvckdGPC8lKXN0cmV0Y2h5R0Y/LyUqc3ltbWV0cmljR0Y/LyUobGFyZ2VvcEdGPy8lLm1vdmFibGVsaW1pdHNHRj8vJSdhY2NlbnRHRj8vJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GMTYmRjMtRiM2Jy1GRjYmUSIyRidGN0Y9RklGN0Y6Rj1GQEZLRk5GN0Y9RklGN0Y9RklGN0Y9Rkk= do not change; these constraints are of the form LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUklbXN1YkdGJDYmLUkjbW9HRiQ2L1EmJmFuZDtGJy8lJXNpemVHUSMyNkYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ25vcm1hbEYnLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSlzdHJldGNoeUdRJXRydWVGJy8lKnN5bW1ldHJpY0dGNy8lKGxhcmdlb3BHRjcvJS5tb3ZhYmxlbGltaXRzR0Y3LyUnYWNjZW50R0Y3LyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGTC1GIzYnLUkjbWlHRiQ2J1EiWUYnL0YzUSMxNkYnLyUnaXRhbGljR0ZBRjUvRjlRJ2l0YWxpY0YnRlVGV0Y1RlkvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJy9JK21zZW1hbnRpY3NHRiRRJ2F0b21pY0YnLUYvNi9RIn5GJ0ZVRjVGOEY7Rj0vRkBGN0ZCRkRGRkZIL0ZLUSYwLjBlbUYnL0ZORmBvLUZSNidRLmRvZXNOb3RDaGFuZ2VGJ0ZVRldGNUZZLUkobWZlbmNlZEdGJDYmLUYjNiktRiw2Ji1GUjYnUSJ5RidGVUZXRjVGWS1GIzYnLUkjbW5HRiQ2JlEiMUYnRlVGNUY4RlVGV0Y1RllGZW5GaG4tRi82L1EiLEYnRlVGNUY4RjsvRj5GQUZeb0ZCRkRGRkZIRl9vL0ZOUSwwLjMzMzMzMzNlbUYnLUYsNiZGXHAtRiM2Jy1GYnA2JlEiMkYnRlVGNUY4RlVGV0Y1RllGZW5GaG5GZXAtRlI2J1EidEYnRlVGV0Y1RllGNUY4RlVGNUY4RjVGOA== where LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYsLUkjbWlHRiQ2J1EiWUYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYvUSJ+RidGL0Y1L0Y5USdub3JtYWxGJy8lJmZlbmNlR0Y3LyUqc2VwYXJhdG9yR0Y3LyUpc3RyZXRjaHlHRjcvJSpzeW1tZXRyaWNHRjcvJShsYXJnZW9wR0Y3LyUubW92YWJsZWxpbWl0c0dGNy8lJ2FjY2VudEdGNy8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlFGOy1GPDYvUSI9RidGL0Y1Rj9GQUZDRkVGR0ZJRktGTS9GUFEsMC4yNzc3Nzc4ZW1GJy9GU0ZYLUkobWZlbmNlZEdGJDYmLUYjNigtSSVtc3ViR0YkNiYtRiw2J1EieUYnRi9GMkY1RjgtRiM2Jy1JI21uR0YkNiZRIjFGJ0YvRjVGP0YvRjJGNUY4LyUvc3Vic2NyaXB0c2hpZnRHUSIwRicvSSttc2VtYW50aWNzR0YkUSdhdG9taWNGJy1GPDYvUSIsRidGL0Y1Rj9GQS9GREY0RkVGR0ZJRktGTUZPL0ZTUSwwLjMzMzMzMzNlbUYnLUZqbjYmRlxvLUYjNictRmJvNiZRIjJGJ0YvRjVGP0YvRjJGNUY4RmVvRmhvRi9GNUY/Ri9GNUY/LUY8Ni9RJSZuZTtGJ0YvRjVGP0ZBRkNGRUZHRklGS0ZNRldGWS1GZW42Ji1GIzYoLUZqbjYmLUYsNidRInhGJ0YvRjJGNUY4Rl9vRmVvRmhvRltwLUZqbjYmRmFxRmNwRmVvRmhvRi9GNUY/Ri9GNUY/Ri9GNUY/ is adjacent to LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA==. We let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1E1b25lQWRqYWNlbnRUaWxlTW92ZWRGJy8lJXNpemVHUSMxNkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjUvRjlRJ25vcm1hbEYn denote the constraint that one tile adjacent to LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== moves to square LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== at time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=. The slide transition constraints are of the form LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2J1EtZXF1YWxUb0JsYW5rRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYqLUYsNidRImlGJ0YvRjJGNUY4LUkjbW9HRiQ2L1EiLEYnRi9GNS9GOVEnbm9ybWFsRicvJSZmZW5jZUdGNy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y3LyUqc3ltbWV0cmljR0Y3LyUobGFyZ2VvcEdGNy8lLm1vdmFibGVsaW1pdHNHRjcvJSdhY2NlbnRHRjcvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GLDYnUSJqRidGL0YyRjVGOEZDLUYsNidRInRGJ0YvRjJGNUY4Ri9GNUZHRi9GNUZHLUZENi9RKiZJbXBsaWVzO0YnRi9GNUZHRkkvRkxGNy9GTkY0Rk9GUUZTRlUvRlhRLDAuMjc3Nzc3OGVtRicvRmVuRmNvLUYsNidRNW9uZUFkamFjZW50VGlsZU1vdmVkRidGL0YyRjVGOEY7Ri9GNUZH for all squares LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA== and timesteps LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=. # Returns a constraint that states square (i, j) does not contain the blank tile at time t equalToBlank := (i, j, t) -> S[i, j, 16, t]: # Returns a constraint saying exactly one tile adjacent to (i, j) changes at time t oneAdjacentTileMoved := proc(i, j, t) local x, y, n; return &or(seq(&and(swapSquares(x[1], x[2], i, j, t), seq(doesNotChange(y[1], y[2], t), y in adjacent(i, j) minus {x}) ), x in adjacent(i, j))); end proc: # Returns slide transition constraints up to timestep M slideTransitionConstraints := proc(M) local t, j, i; return seq(seq(seq(equalToBlank(i, j, t) &implies oneAdjacentTileMoved(i, j, t), i=1..4), j=1..4), t=0..M-1); end proc:

JSFHJSFH

Finally, we need to encode the starting position (the board state at time 0) and ending position of the puzzle. We let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1Ezc3RhcnRpbmdDb25zdHJhaW50RicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJ0Y1L0Y5USdub3JtYWxGJw== denote the constraint saying the board starts in its starting position and let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2J1EyZW5kaW5nQ29uc3RyYWludHNGJy8lJXNpemVHUSMxNkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUkobWZlbmNlZEdGJDYmLUYjNictRiw2J1EiTkYnRi9GMkY1RjgtSSNtb0dGJDYvUSIsRidGL0Y1L0Y5USdub3JtYWxGJy8lJmZlbmNlR0Y3LyUqc2VwYXJhdG9yR0Y0LyUpc3RyZXRjaHlHRjcvJSpzeW1tZXRyaWNHRjcvJShsYXJnZW9wR0Y3LyUubW92YWJsZWxpbWl0c0dGNy8lJ2FjY2VudEdGNy8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHUSwwLjMzMzMzMzNlbUYnLUYsNidRIk1GJ0YvRjJGNUY4RjVGR0YvRjVGR0Y1Rkc= denote the constraint saying the board is solved sometime between timesteps LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EiTkYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EiTUYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic=. startingPosition := [[5, 1, 7, 3], [9, 2, 11, 4], [13, 6, 15, 8], [16, 10, 14, 12]]: # Returns a constraint which says that the board is solved at time t boardSolved := proc(t) local i, j; return &and(seq(seq(S[i, j, 4*(i-1)+j, t], i=1..4), j=1..4)); end proc: # Returns a constraint defining the initial position of the board state startingConstraint := &and(seq(seq(S[i, j, startingPosition[i, j], 0], i=1..4), j=1..4)): # Returns a constraint saying the board is solved between timesteps N and M endingConstraints := proc(N, M) local t; return &or(seq(boardSolved(t), t=N..M)); end proc:

We use the Satisfy command from the Logic package which finds a satisfying assignment of a logical formula if one exists. We use the time command to measure how quickly the solution is found. For efficiency reasons we only start looking for solutions with at most 5 moves; if no solution is found then we look for solutions using at most 10 moves and continue in this manner until a solution is found. M := 5: satisfyingAssignment := NULL: while satisfyingAssignment = NULL and M <= 80 do allConstraints := noSquareHasTwoTiles(M), staticTransitionConstraints(M), slideTransitionConstraints(M), startingConstraint, endingConstraints(M-4, M): printf("Generated %d constraints with %d variables", nops([allConstraints]), nops(indets([allConstraints], name))); printf(" and now searching for a solution with at most %d moves...\134n", M); startTime := time[real](); satisfyingAssignment := Logic:-Satisfy(&and(allConstraints)): if satisfyingAssignment = NULL then printf("No solution found with at most %d moves in %.2f seconds.\134n", M, time[real]()-startTime); else printf("Solution found with at most %d moves in %.2f seconds.\134n", M, time[real]()-startTime); end if; M += 5; end do:

The state of the board at each timestep LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= is determined by iterating over the set returned by Satisfy and checking which variables were assigned to true. digits := Array(1..4, 1..4, 0..M): for eq in satisfyingAssignment do if rhs(eq) then i, j, n, t := op(lhs(eq)); digits[i, j, t] := n; end if; end do: Once a solved state is reached any additional moves are irrelevant and we ignore them in the visualization. We let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EpbnVtTW92ZXNGJy8lJXNpemVHUSMxNkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjUvRjlRJ25vcm1hbEYn represent the length of the shortest found solution. if satisfyingAssignment = NULL then numMoves := 0: else numMoves := M: for t from 0 to M do if ArrayTools:-IsEqual(digits[1..4, 1..4, t], Array([seq([seq(4*(j-1)+i, i=1..4)], j=1..4)])) then numMoves := t; break; end if; end do: end if: We'll use commands from the plots and plottools packages to draw a visual representation of a 15-puzzle board. The commands to draw the tiles will be stored in an array LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EtcGxvdENvbW1hbmRzRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJ0Y1L0Y5USdub3JtYWxGJw==. To smoothen out the animation we use a parameter LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EkcmVzRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJ0Y1L0Y5USdub3JtYWxGJw== to control the "resolution" of the animation, i.e., number of individual frames drawn in each timestep. The commands for the LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWZlbmNlZEdGJDYmLUYjNictSSNtaUdGJDYnUSJpRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIixGJ0Y0RjovRj5RJ25vcm1hbEYnLyUmZmVuY2VHRjwvJSpzZXBhcmF0b3JHRjkvJSlzdHJldGNoeUdGPC8lKnN5bW1ldHJpY0dGPC8lKGxhcmdlb3BHRjwvJS5tb3ZhYmxlbGltaXRzR0Y8LyUnYWNjZW50R0Y8LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRjE2J1EiakYnRjRGN0Y6Rj1GOkZERjRGOkZERjpGRA==th tile at real time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EickYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= (where LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EickYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= will be a real number between 0 and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EpbnVtTW92ZXNGJy8lJXNpemVHUSMxNkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdRJmZhbHNlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnRjUvRjlRJ25vcm1hbEYn) will be stored in LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2J1EtcGxvdENvbW1hbmRzRicvJSVzaXplR1EjMTZGJy8lJ2l0YWxpY0dRJXRydWVGJy8lK2V4ZWN1dGFibGVHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2KC1GIzYqLUYsNidRImlGJ0YvRjJGNUY4LUkjbW9HRiQ2L1EiLEYnRi9GNS9GOVEnbm9ybWFsRicvJSZmZW5jZUdGNy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y3LyUqc3ltbWV0cmljR0Y3LyUobGFyZ2VvcEdGNy8lLm1vdmFibGVsaW1pdHNHRjcvJSdhY2NlbnRHRjcvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GLDYnUSJqRidGL0YyRjVGOEZDLUYsNidRJmZsb29yRidGLy9GM0Y3RjVGRy1GPDYmLUYjNictRiw2J1EickYnRi9GMkY1RjgtRkQ2L1EnJnNkb3Q7RidGL0Y1RkdGSS9GTEY3Rk1GT0ZRRlNGVUZXL0ZlbkZZLUYsNidRJHJlc0YnRi9GMkY1RjhGNUZHRi9GNUZHRjVGR0YvRjVGRy8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJ0Y1Rkc=. with(plots): with(plottools): drawBoard := rectangle([1,1], [5,5], thickness=3, color="Gray"): # Returns the commands to draw a tile with center at point (x, y) and label n drawTile := proc(x, y, n) return textplot([x, y, n], font = [Arial, roman, 24]), rectangle([x-0.5,y+0.5], [x+0.5,y-0.5], color=`if`(n-floor((n-1)/4) mod 2=1, "LightBlue", "White")); end proc: res := 10: plotCommands := Array(1..4, 1..4, 0..res*numMoves): for i from 1 to 4 do for j from 1 to 4 do for t from 0 to res*numMoves do r := t/res; # real time it := floor(r); # integer time n := digits[i, j, it]; # If blank tile, draw nothing if n = 16 then plotCommands[i, j, t] := NULL; # If tile is sliding between time it and it+1 elif it < M and digits[i, j, it+1] = 16 then if i > 1 and digits[i-1, j, it] = 16 then # Tile sliding downwards plotCommands[i, j, t] := drawTile(j+0.5, -i+5.5+r-it, n); elif j > 1 and digits[i, j-1, it] = 16 then # Tile sliding right plotCommands[i, j, t] := drawTile(j+0.5-r+it, -i+5.5, n); elif i < 4 and digits[i+1, j, it] = 16 then # Tile sliding upwards plotCommands[i, j, t] := drawTile(j+0.5, -i+5.5-r+it, n); elif j < 4 and digits[i, j+1, it] = 16 then # Tile sliding left plotCommands[i, j, t] := drawTile(j+0.5+r-it, -i+5.5, n); end if; # If tile is static between time it and it+1 else plotCommands[i, j, t] := drawTile(j+0.5, -i+5.5, n); end if; end do: end do: end do: We'll use the Explore command to allow us to see how the board state changes over time with a slider controlling what time LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EidEYnLyUlc2l6ZUdRIzE2RicvJSdpdGFsaWNHUSV0cnVlRicvJStleGVjdXRhYmxlR1EmZmFsc2VGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRidGNS9GOVEnbm9ybWFsRic= to view. # Returns the commands to draw the state of the game at real time r plotCommandsRealTime := proc(r) return entries(plotCommands[1..4, 1..4, floor(r*res)], nolist); end proc: if numMoves > 0 then Explore(display(plotCommandsRealTime(k), drawBoard, scaling=constrained, axes=none), parameters=[[k=0..evalf(numMoves),label="t"]]): else display(plotCommandsRealTime(0), drawBoard, scaling=constrained, axes=none); printf("No solution found.\134n"); end if;

JSFH