{"id":2203,"date":"2020-09-14T22:24:17","date_gmt":"2020-09-14T20:24:17","guid":{"rendered":"https:\/\/blog.atlant.is\/?p=2203"},"modified":"2021-02-21T13:33:59","modified_gmt":"2021-02-21T11:33:59","slug":"classic-15-puzzle","status":"publish","type":"post","link":"https:\/\/blog.douzeb.is\/?p=2203","title":{"rendered":"Classic 15 Puzzle"},"content":{"rendered":"\n<div class=\"is-layout-flow wp-block-group\"><div class=\"wp-block-group__inner-container\">\n<iframe id=\"auto-iframe\" name=\"auto-iframe\" src=\"https:\/\/fredatatlantis.github.io\/FifteenPuzzle.js\/fifteenpuzzle.html\" width=\"100%\" height=\"400\" frameborder=\"0\" scrolling=\"no\"><\/iframe>\n\n\n\n<div style=\"text-align:center;font-family:Inter,sans-serif;font-size:15px;color:gray\">15-puzzle by Mark Rohlich<\/figcaption><\/div>\n<\/div><\/div>\n\n\n\n<h2>Genesis<\/h2>\n\n\n\n<p>The Fifteen Puzzle consists of fifteen numbered square tiles in a 4\u00d74 square grid, with one position empty or blank. Any tile horizontally or vertically adjacent to the blank can be moved into the blank position. The task is to rearrange the tiles from some random initial configuration into a desired goal configuration, ideally or optimally using the fewest moves possible.<\/p>\n\n\n\n<!--more-->\n\n\n\n<blockquote class=\"wp-block-quote\"><p>The Fifteen Puzzle was invented by Sam Loyd<span id='easy-footnote-1-2203' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/blog.douzeb.is\/?p=2203#easy-footnote-bottom-1-2203' title='Although this is &lt;a href=&quot;https:\/\/en.wikipedia.org\/wiki\/15_puzzle&quot;&gt;disputed&lt;\/a&gt;.'><sup>1<\/sup><\/a><\/span> in the 1870s <span class=\"zp-InText-zp-ID--6833562-DA682IHW--wp2203 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:DA682IHW}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span>, and appeared in the scientific literature shortly thereafter <span class=\"zp-InText-zp-ID--6833562-929MI6GN--wp2203 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:929MI6GN}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span>. The editor of the journal added the following comment to the paper: \u201cThe \u201815\u2019 puzzle for the last few weeks has been prominently before the American public, and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community.\u201d<\/p><p>One reason for the world-wide Fifteen Puzzle craze was that Loyd offered a $1000 cash prize to transform a particular initial state to a particular goal state. Johnson and Story proved that it wasn\u2019t possible, that the entire state space was divided into even and odd permutations, and that there is no way to transform one into the other by legal moves.<\/p><cite><span class=\"zp-InText-zp-ID--6833562-Q2GV7Z5H--wp2203 zp-InText-Citation loading\" rel=\"{ 'pages': 'np', 'items': '{6833562:Q2GV7Z5H}', 'format': '(%a%, %d%, %p%)', 'brackets': '', 'etal': '', 'separator': '', 'and': '' }\"><\/span><\/cite><\/blockquote>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-loyd.png\" class=\"aligncenter\" style=\"width:300px;height:auto;\">\n<div style=\"text-align:center;\">\nLoyd&rsquo;s impossible goal state with a \\$1000 cash prize\n<\/div>\n\n\n\n\n\n<p><\/p>\n\n\n\n<h2>Proof of insolvability<\/h2>\n\n\n\n<p>The classical proof<span id='easy-footnote-2-2203' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/blog.douzeb.is\/?p=2203#easy-footnote-bottom-2-2203' title='As given on &lt;a href=&quot;https:\/\/en.wikipedia.org\/wiki\/15_puzzle&quot;&gt;wikipedia&lt;\/a&gt; or &lt;a href=&quot;https:\/\/www.youtube.com\/watch?v=YI1WqYKHi78&amp;amp;vl=fr&quot;&gt;numberphile&lt;\/a&gt;.'><sup>2<\/sup><\/a><\/span> for the insolvability of the puzzle involves an argument on:<\/p>\n\n\n\n<ul><li>the&nbsp;parity<span id='easy-footnote-3-2203' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/blog.douzeb.is\/?p=2203#easy-footnote-bottom-3-2203' title='Refer to section &lt;a href=&quot;#cheatsheet&quot; data-type=&quot;internal&quot; data-id=&quot;#cheatsheet&quot;&gt;cheatsheet&lt;\/a&gt; for permutations notations and the definition of parity.'><sup>3<\/sup><\/a><\/span> of the permutation&nbsp;of the squares on the grid,<\/li><li>versus the parity of the&nbsp;taxicab distance&nbsp;(number of rows plus number of columns) traveled by the blank square<\/li><\/ul>\n\n\n\n<p>A summertime conversation with G.R., who was not aware of the question or the proof, lead to his suggesting a subtle and interesting variant which fully dispenses with the blank square. Here it goes&#8230;<\/p>\n\n\n\n<h2>Variant<\/h2>\n\n\n\n<p>The classical insolvability proof works by identifying the set of possible puzzle states with the group $\\mathcal{S}_{16}$ of permutations of the squares on the puzzle grid. Instead for the variant we work with the group $\\mathcal{S}_{18}$ of permutations of the  <em>fifteen<\/em> tiles plus <em>three<\/em> fictitious elements $a$, $b$, $c$, which represent the horizontal separations between the rows of the puzzle.<\/p>\n\n\n\n<h3>Puzzle states<\/h3>\n\n\n\n<p>As shown in the picture below, the initial state of the puzzle is represented by the identity permutation in $\\mathcal{S}_{18}$:<\/p>\n\n\n\n<p>$$\\text{Id} =<br>\\left(<br>\\begin{array}{l}<br>1\\;2\\;3\\;4\\;a\\;5\\;6\\;7\\;8\\;b\\;9\\;10\\;11\\;12\\;c\\;13\\;14\\;15\\\\<br>1\\;2\\;3\\;4\\;a\\;5\\;6\\;7\\;8\\;b\\;9\\;10\\;11\\;12\\;c\\;13\\;14\\;15<br>\\end{array}<br>\\right)$$<\/p>\n\n\n\n<table style=\"border-style:none;\">\n\n<tr style=\"border-style:none;\"><td style=\"border-style:none;text-align:center;\">\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-phy-1.png\" class=\"aligncenter\" style=\"width:295;height:272;\">\n<\/td><td style=\"border-style:none;text-align:center;\">\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-s18-1.png\" class=\"aligncenter\" style=\"width:331;height:242;\">\n<\/td><\/tr>\n<tr style=\"border-style:none;\"><td style=\"border-style:none;text-align:center;\">\nInitial puzzle state\n<\/td><td style=\"border-style:none;text-align:center;\">Element of $\\mathcal{S}_{18}\n$<\/td><\/tr>\n\n<\/table>\n\n\n\n<p>Note that moving a tile horizontally does not change the representation in $\\mathcal{S}_{18}$, but moving a tile vertically does:<\/p>\n\n\n\n<table style=\"border-style:none;\">\n\n<tr style=\"border-style:none;\"><td style=\"border-style:none;text-align:center;\">\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-phy-2.png\" class=\"aligncenter\" style=\"width:295;height:272;\">\n<\/td><td style=\"border-style:none;text-align:center;\">\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-s18-2.png\" class=\"aligncenter\" style=\"width:331;height:242;\">\n<\/td><\/tr>\n\n<tr style=\"border-style:none;\"><td style=\"border-style:none;text-align:center;\">\nAfter moving tile $11$ down\n<\/td><td style=\"border-style:none;text-align:center;\">Element of $\\mathcal{S}_{18}\n$<\/td><\/tr>\n\n<\/table>\n\n\n\n<p>After tile $11$ has been moved down, the representation of the puzzle becomes:<\/p>\n\n\n\n<p>\\begin{align*}<br>&amp;\\left(<br>\\begin{array}{l}<br>1\\;2\\;3\\;4\\;a\\;5\\;6\\;7\\;8\\;b\\;9\\;10\\;11\\;12\\;c\\;\\;13\\;14\\;15\\\\<br>1\\;2\\;3\\;4\\;a\\;5\\;6\\;7\\;8\\;b\\;9\\;10\\;12\\;\\;c\\;13\\;14\\;11\\;15<br>\\end{array}<br>\\right)\\\\<br>\\\\<br>=&amp;(11\\;12\\;c\\;13\\;14)\\quad \\text{(cycle of length 5)}<br>\\end{align*}<\/p>\n\n\n\n<p>Let $\\mathcal{P} \\subset \\mathcal{S}_{18}$ be the set of (representations of) all possible puzzle states, legal and non-legal. Then $\\mathcal{P}$ is precisely:<\/p>\n\n\n\n<p>$$\\mathcal{P} = \\left\\{s\\in\\mathcal{S}_{18}\\quad<br>\\left|\\quad<br>\\begin{array}{ll}<br>&amp;\\big(s(4)=a\\;\\text{and}\\;s(8)=b\\;\\text{and}\\;s(12)=c\\big)\\\\<br>\\text{or}&amp;\\big(s(4)=a\\;\\text{and}\\;s(8)=b\\;\\text{and}\\;s(c)=c\\big)\\\\<br>\\text{or}&amp;\\big(s(4)=a\\;\\text{and}\\;s(b)=b\\;\\text{and}\\;s(c)=c\\big)\\\\<br>\\text{or}&amp;\\big(s(a)=a\\;\\text{and}\\;s(b)=b\\;\\text{and}\\;s(c)=c\\big)<br>\\end{array}<br>\\right.<br>\\;<br>\\right\\}<br>$$<\/p>\n\n\n\n<h3>Tile moves<\/h3>\n\n\n\n<p>We sort tile moves according to their <em>type<\/em>, where there are exactly 24 types as shown in the following picture:<\/p>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-types.png\" class=\"aligncenter\" style=\"width:300px;height:auto;\">\n<div style=\"text-align:center;\">\n$2\\cdot3\\cdot4=24$ types of moves\n<\/div>\n\n\n\n<p>For instance, type $\\downarrow_{c3}$ gather all moves like so:<\/p>\n\n\n\n<ul><li>downwards,<\/li><li>crossing separator $c$,<\/li><li>in column $3$.<\/li><\/ul>\n\n\n\n<img decoding=\"async\" src=\"https:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/fifteen-dc3.png\" class=\"aligncenter\" style=\"width:300px;height:auto;\">\n<div style=\"text-align:center;\">\nThis is move type $\\downarrow_{c3}$\n<\/div>\n\n\n\n<p>Let $\\mathcal{M}\\subset\\mathcal{P}\\times\\mathcal{P}$ be the set of (representations of) all possible tile moves, where $(s, e)\\in\\mathcal{M}$ is the move starting at $s$ and ending at $e$. Finally let us split $\\mathcal{M}$ along move types:<\/p>\n\n\n\n<p>$$\\mathcal{M}\\quad=\\;\\;\\bigcup_{\\text{all types }t}\\mathcal{M}_t$$<\/p>\n\n\n\n<h3>Tile moves are cycles<\/h3>\n\n\n\n<p>Lemma: all moves in $\\mathcal{M}$ are cycles of length $5$.<\/p>\n\n\n\n<p>We verify this by considering every move type in turn.<\/p>\n\n\n\n<p>For example, $\\forall (s, e)\\in\\mathcal{M}_{\\downarrow_{c3}}$:<\/p>\n\n\n\n<p>$$\\begin{array}{l}<br>e&amp;=\\left(<br>\\begin{array}{l}<br>\\;\\;1\\;\\;\\;\\;2\\;\\;\\;\\;3\\;\\;\\;\\;4\\;\\;\\;\\;\\,a\\;\\;\\;\\;5\\;\\;\\;\\;6\\;\\;\\;\\;7\\;\\;\\;\\;8\\;\\;\\;b \\\\<br>s(1) s(2) s(3) s(4) \\;a\\;s(5) s(6) s(7) s(8) b<br>\\end{array}<br>\\right. \\\\<br>&amp;\\\\<br>&amp;\\quad\\quad\\left.<br>\\begin{array}{l}<br>\\;\\;\\;9\\;\\;\\;\\;10\\;\\;\\;\\;11\\;\\;\\;12\\;\\;\\;\\;c\\;\\;\\;\\;\\;13\\;\\;\\;\\;14\\;\\;\\;\\;15 \\\\<br>s(9) s(10) s(12)\\;\\;c\\;s(13) s(14) s(11) s(15)<br>\\end{array}<br>\\right) \\\\<br>&amp;\\\\<br>&amp;=\\;\\; (11\\;\\;12\\;\\;c\\;\\;13\\;\\;14)\\circ s,<br>\\end{array}$$<\/p>\n\n\n\n<p>which gives $e \\circ s^{-1} = (11\\;\\;12\\;\\;c\\;\\;13\\;\\;14)$.<\/p>\n\n\n\n<p>And so on<span id='easy-footnote-4-2203' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/blog.douzeb.is\/?p=2203#easy-footnote-bottom-4-2203' title='&lt;br&gt;\\begin{array}{|c|c|}&lt;br&gt;\\hline&lt;br&gt;(s,e)\\in&amp;amp;e\\circ s^{-1} =\\\\&lt;br&gt;\\hline&lt;br&gt;\\mathcal{M}_{\\downarrow_{a1}}&amp;amp;(1\\;2\\;3\\;4\\;a)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{a2}}&amp;amp;(2\\;3\\;4\\;a\\;5)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{a3}}&amp;amp;(3\\;4\\;a\\;5\\;6)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{a4}}&amp;amp;(4\\;a\\;5\\;6\\;7)\\\\&lt;br&gt;\\hline&lt;br&gt;\\mathcal{M}_{\\downarrow_{b1}}&amp;amp;(5\\;6\\;7\\;8\\;b)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{b2}}&amp;amp;(6\\;7\\;8\\;b\\;9)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{b3}}&amp;amp;(7\\;8\\;b\\;9\\;10)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{b4}}&amp;amp;(8\\;b\\;9\\;10\\;11)\\\\&lt;br&gt;\\hline&lt;br&gt;\\mathcal{M}_{\\downarrow_{c1}}&amp;amp;(9\\;10\\;11\\;12\\;c)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{c2}}&amp;amp;(10\\;11\\;12\\;c\\;13)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{c3}}&amp;amp;(11\\;12\\;c\\;13\\;14)\\\\&lt;br&gt;\\mathcal{M}_{\\downarrow_{c4}}&amp;amp;(12\\;c\\;13\\;14\\;15)\\\\&lt;br&gt;\\hline&lt;br&gt;\\end{array}&lt;br&gt;'><sup>4<\/sup><\/a><\/span>&#8230; Hence all moves are cycles of length $5$ and even parity:<\/p>\n\n\n\n<p>$$<br>\\forall (s, e) \\in \\mathcal{M}, \\quad \\pi(e \\circ s^{-1}) = 1<br>$$<\/p>\n\n\n\n<h3>Conclusion<\/h3>\n\n\n\n<p>Consider a <em>legal<\/em> puzzle state $s\\in\\mathcal{P}$. There exists a sequence of moves $(s_0,e_0), \\cdots, (s_n,e_n)$ in $\\mathcal{M}$, such that:<\/p>\n\n\n\n<p>$$<br>\\left\\{<br>\\begin{array}{l}<br>s_0=\\text{Id}\\\\<br>\\forall i &lt; n,\\quad s_{i+1}=e_i\\\\<br>e_n=s<br>\\end{array}<br>\\right.<br>$$<\/p>\n\n\n\n<p>It follows that:<\/p>\n\n\n\n<p>\\begin{align*}<br>s&amp;=e_n\\circ(s_n^{-1}\\circ e_{n-1})\\circ\\cdots\\circ(s_1^{-1}\\circ e_0)\\circ\\text{Id}\\\\<br>&amp;=(e_n\\circ s_n^{-1})\\circ(e_{n-1}\\circ s_{n-1}^{-1})\\circ\\cdots\\circ (e_1\\circ s_1^{-1})\\circ(e_0\\circ s_0^{-1})<br>\\end{align*}<\/p>\n\n\n\n<p>is a permutation with even parity.<\/p>\n\n\n\n<p>Hence Loyd&rsquo;s \\$1000-cash puzzle goal state is not legal.$\\quad\\Box$<\/p>\n\n\n\n<h2>References<\/h2>\n\n\n\n\n<div id='zp-InTextBib-zotpress-53b94e3bca361361d03a2e95ce033dcb' class='zp-Zotpress zp-Zotpress-InTextBib wp-block-group zp-Post-2203'>\r\n\t\t<span class=\"ZP_ITEM_KEY\" style=\"display: none;\">{6833562:DA682IHW};{6833562:929MI6GN};{6833562:Q2GV7Z5H}<\/span>\r\n\t\t<span class=\"ZP_STYLE\" style=\"display: none;\">apa<\/span>\r\n\t\t<span class=\"ZP_SORTBY\" style=\"display: none;\">default<\/span>\r\n\t\t<span class=\"ZP_ORDER\" style=\"display: none;\">asc<\/span>\r\n\t\t<span class=\"ZP_TITLE\" style=\"display: none;\">no<\/span>\r\n\t\t<span class=\"ZP_SHOWIMAGE\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_SHOWTAGS\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_DOWNLOADABLE\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_NOTES\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_ABSTRACT\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_CITEABLE\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_TARGET\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_URLWRAP\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_FORCENUM\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_HIGHLIGHT\" style=\"display: none;\"><\/span>\r\n\t\t<span class=\"ZP_POSTID\" style=\"display: none;\">2203<\/span><div class='zp-List loading'>\n<div class=\"zp-SEO-Content\"><div id=\"zp-ID-2203-6833562-DA682IHW\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Gardner, M. (Ed.). (1960). <i>More mathematical puzzles of Sam Loyd<\/i>. Dover Publ.<\/div>\n<\/div><\/div><div id=\"zp-ID-2203-6833562-929MI6GN\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Johnson, Wm. W., &amp; Story, W. E. (1879). Notes on the &#x201C;15&#x201D; Puzzle. <i>American Journal of Mathematics<\/i>, <i>2<\/i>(4), 397&#x2013;404. JSTOR. <a href='https:\/\/doi.org\/10.2307\/2369492'>https:\/\/doi.org\/10.2307\/2369492<\/a><\/div>\n<\/div><\/div><div id=\"zp-ID-2203-6833562-Q2GV7Z5H\" class=\"zp-Entry zpSearchResultsItem\"><div class=\"csl-bib-body\" style=\"line-height: 2; padding-left: 1em; text-indent:-1em;\">\n  <div class=\"csl-entry\">Korf, R. E. (2000). Recent Progress in the Design and Analysis of Admissible Heuristic Functions. In B. Y. Choueiry &amp; T. Walsh (Eds.), <i>Abstraction, Reformulation, and Approximation<\/i> (pp. 45&#x2013;55). Springer. <a href='https:\/\/doi.org\/10.1007\/3-540-44914-0_3'>https:\/\/doi.org\/10.1007\/3-540-44914-0_3<\/a><\/div>\n<\/div><\/div><\/div><!-- .zp-zp-SEO-Content -->\n<\/div><!-- .zp-List --><\/div><!--.zp-Zotpress-->\n\n\n\n\n\n<hr class=\"wp-block-separator is-style-default\"\/>\n\n\n\n<h2 id=\"cheatsheet\">Permutations cheatsheet<\/h2>\n\n\n\n<p>A <em>permutation<\/em> of the set $\\{1, 2, \\cdots, n\\}$ is a bijection of $\\{1, 2, \\cdots, n\\}$ with itself. The set of permutations of $\\{1, 2, \\cdots, n\\}$<span id='easy-footnote-5-2203' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/blog.douzeb.is\/?p=2203#easy-footnote-bottom-5-2203' title='or for that matter, of any set of finite cardinal $n\\in\\mathbb{N}$.'><sup>5<\/sup><\/a><\/span> is denoted by $\\mathcal{S}_n$.<\/p>\n\n\n\n<p>One usual way of writing a permutation $p$ is by providing the exhaustive list of $x \\mapsto p(x)$ mappings, in a rectangular matrix like so:<\/p>\n\n\n\n<p>$$p=\\left(\\begin{array}{cccccc}<br>1&amp;2&amp;3&amp;4&amp;5&amp;6&amp;7\\\\<br>7&amp;3&amp;5&amp;2&amp;4&amp;6&amp;1<br>\\end{array}\\right)$$<\/p>\n\n\n\n<p>A more concise way is by specifying $p$ as a combination of <em>cycles<\/em>. For example:<\/p>\n\n\n\n<p>$$p = (1\\;\\;7) (2\\;\\;3\\;\\;5\\;\\;4)$$<\/p>\n\n\n\n<p>A permutation that consists of a single length-2 cycle is called a <em>transposition<\/em>. Every permutation in $\\mathcal{S}_n$ can be expressed as a <em>composition<\/em> of tranpositions. For example:<\/p>\n\n\n\n<p>$$(1\\;\\;7) (2\\;\\;3\\;\\;5\\;\\;4) = (1\\;\\;7)\\circ(2\\;\\;3)\\circ(3\\;\\;5)\\circ(5\\;\\;4)$$<\/p>\n\n\n\n<p>The operation of composition gives the set $\\mathcal{S}_n$ a structure of <em>group<\/em>. There is a unique group morphism from $\\big(\\mathcal{S}_n, \\circ\\big)$ to $\\big(\\{-1,1\\},\\cdot\\big)$ which maps transpositions to the value -1. This morphism is called <em>parity<\/em>  (denoted by $\\pi$ in this article).<\/p>\n\n\n\n<p>$$\\pi: \\mathcal{S}_n \\rightarrow \\{-1,1\\}$$<\/p>\n\n\n\n<p>$$\\forall x, y \\in \\mathcal{S}_n, \\;\\;\\pi(y\\circ x) = \\pi(y)\\cdot\\pi(x)$$<\/p>\n\n\n\n<p>A cycle of length even (respectively odd) has parity odd (respectively even).<\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>15-puzzle by Mark Rohlich Genesis The Fifteen Puzzle consists of fifteen numbered square tiles in a 4\u00d74 square grid, with one position empty or blank. Any tile horizontally or vertically adjacent to the blank can be moved into the blank position. The task is to rearrange the tiles from some random initial configuration into a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":2485,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,19],"tags":[],"ppma_author":[76],"authors":[{"term_id":76,"user_id":1,"is_guest":0,"slug":"fred","display_name":"Fred","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/ec0326d654fdf9f66e9eb42bb34a9bc4?s=96&d=mm&r=g","description":"","first_name":"","last_name":"","user_url":""}],"_links":{"self":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/2203"}],"collection":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2203"}],"version-history":[{"count":386,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/2203\/revisions"}],"predecessor-version":[{"id":3492,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/2203\/revisions\/3492"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/media\/2485"}],"wp:attachment":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2203"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2203"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2203"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fppma_author&post=2203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}