Talk:15 Puzzle

Untitled

For inclusion: puzzle history at this page— Preceding unsigned comment added by MacGyverMagic (talk • contribs) 08:22, 25 October 2004 (UTC)

Solution

The page states that there IS a hueristic to solve it, but doesn't give that solution. We definitely need this... Fieari 18:08, 29 August 2006 (UTC)

---

There is an actual solution. I can't describe it in detail, but it involves solving the top two rows first, then the bottom row. If done correctly, the third row solves itself. 75.73.231.136 23:19, 5 August 2007 (UTC)

1) We need to distinguish a 'human-like' solution from a more optimal (in terms of minimal number of moves) solution. a) A human like solution would be based on considering one tile at a time (and on a higher level, one row at a time) b) A computer solution could consider more or even all tiles at a time

2) About the human algorithm

I think we need to be more specific on 'done correctly' as described above. It's actually the trickiest part of the puzzle. Actually, I made an algorithm that does row 1 first, then row 2 and then row 3 and 4 together by rolling up row 3 into the left lower 2x2 square and row 4 in the right lower 2x2 square. Since the last row only has 3 tiles, it can always be reordered in the right order in the lower 2x2 square together with the hole. An illustrative video is at: http://www.youtube.com/watch?v=vFqTkyU3df8 It analyzes the current state in a long if else statement with many cases and calculates just one step ahead. So it does not search a tree, which would be another option. I could make one that only shows the algorithm. http://www.youtube.com/watch?v=dpS9jZTvQzs also describes it well

3) About the computer algorithm There is a video on YouTube illustrating this algorithm somewhere. Looks entirely different. —Preceding unsigned comment added by Mrcastorp (talk • contribs) 22:03, 4 March 2010 (UTC)

Solvability

I do understand the parity function and that it divides all possible permutations into two classes: The odd and even permutations. However, I don't understand how to prove that given any two permutations from the same class, there is always a series of valid moves that leads from the one to the other. IMHO, this proof is a necessary addition to the solvability argument. Just because we define a parity function that knows only two different outcomes (odd, even) and then prove that valid moves stay within a class, it doesn't mean that maybe there really are four different classes and any valid move stays inside those, too. That's purely hypothetically of course, I know that the solvability argument given in the argument is true for any n-puzzle, but for me it's not proven yet. jlh (talk) 23:34, 12 December 2008 (UTC)

Rephrasing your question, since obviously all solvable permutations will be even, and all odd permutations will not be solvable, can there be any even permutations that are not solvable? Actually, even if there are, does it matter? The whole point was that (at least) half the permutations are not solvable... -- Jokes Free4Me (talk) 18:19, 3 September 2009 (UTC)

A second question about this solvability issue could be if the proof (that there are at least N!/2 unsolvable permutations) apply for odd N's too, like it applies for even values of N. Can anyone help with this? -- Jokes Free4Me (talk) 18:19, 3 September 2009 (UTC)

Odd permutations are unsolvable for all sizes of the puzzle. Even permutations are always solvable. The article on Mathworld gives references to the original published proofs (Johnson and Storey), which are available on JSTOR but you will need an account or cash to see them in full. SpinningSpark 21:47, 4 September 2009 (UTC)

The "always" part ("Even permutations are always solvable") is not yet justified in the current form of the article. I'll add info about Archer.

And about that JSTOR proof... it's "© 1879", isn't it in the PD already? -- Jokes Free4Me (talk) 12:33, 10 September 2009 (UTC)

The proof given in this section is different from the proof given in section Alternate proof. This section says:

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner.

But this is not correct. A row move will change the parity of the taxicab distance. But a row move will not change the parity of the permutation. So the parity used in the invariant is changed. --JingguoYao (talk) 07:15, 25 February 2016 (UTC)

Remember that the permutation here includes the empty square, so yes, a row move does change the parity of the permutation (it swaps the empty square with a non-empty square). Perhaps it should be clarified what "the permutation" refers to. Sniffnoy (talk) 15:45, 25 February 2016 (UTC)

It does already say "parity of the permutation of all 16 squares", so obviously that includes the empty square. To explain it any further would be tantamount to explaining that fifteen plus one equals sixteen. SpinningSpark 16:06, 25 February 2016 (UTC)

Thanks. I am clear on this. The invariant is not wrong. --JingguoYao (talk) 01:04, 26 February 2016 (UTC)

No matter where you start when you minimize the distance from the solution there are only two states. You can either end with a distance of 0 (even: 13-14-15-X) or 1 (odd: 13-X-15-14). Any other possible grid can always be reduced further into one of these two states. It can be shown impossible to move only two tiles without disrupting a third. I will note that any odd permutation becomes an even permutation by turning the grid 90 degrees.205.142.232.18 (talk) 20:09, 15 May 2019 (UTC)

Bobby Fischer

A story I think recounted in Profile of a Prodigy has the chess player entering a 15 tournament that happened to be being held in his hotel and he won it.--Jrm2007 (talk) 14:46, 5 March 2010 (UTC)

The article contained an account of Bobby Fischer having appeared on The Tonight Show with Johnny Carson, at which time he demonstrated his prowess at the 15 puzzle. (He solved it in 17 seconds.) This claim was accompanied by a tag stating that a citation was needed. Thinking I was solving this problem, I linked to a YouTube video of Fischer on that episode of The Tonight Show doing the 15 puzzle. https://www.youtube.com/watch?v=QxvnEwvgfeI User:Anita5192 undid my revision, stating that YouTube was not a reliable source! She then deleted the claim about Bobby Fischer altogether, explaining that it had been "unsourced for four years!" This seems ridiculous. The YouTube video documents and proves the truth of the claim. Is anyone seriously claiming that the video is doctored? Krakatoa (talk) 22:08, 22 March 2021 (UTC)

As I wrote in my edit summary, I deleted the claim about Bobby Fischer because it had no source and was marked as unsourced for nearly four years. Regardless of whether the video was doctored or not, YouTube is not a source. See WP:YOUTUBE.—Anita5192 (talk) 04:47, 23 March 2021 (UTC)

Except that that seems to be the verified channel of Johnny Carson's show, and WP:RSPYT (the actual policy) says Content uploaded from a verified official account, such as that of a news organization, may be treated as originating from the uploader and therefore inheriting their level of reliability. Double sharp (talk) 09:05, 24 March 2021 (UTC)

It seems that User:Double sharp is right; the policy banning Youtube does not really apply here. However, that does not necessarily make this - [1] - a valid source. It may appear to document the fact. (Though, isn't it 13:00 to 13:22 he's actually solving it, which is more than 17 seconds? And do you actually see the puzzle being first scrambled, then solved? -- Note: I haven't seen the whole video.) But Wikipedia does not merely report facts; to document notability etc., we usualy need secondary or tertiary sources - which this isn't.--Nø (talk) 11:16, 24 March 2021 (UTC)

Primary sources are not proscribed. The relevant guideline actually says primary sources that have been reputably published may be used in Wikipedia, but only with care, because it is easy to misuse them.

Youtube is generally unreliable but there is no blanket proscription. We do not delete cites to Youtube just because they are on Youtube. We delete them if they are unreliable. SpinningSpark 16:30, 1 August 2021 (UTC)

Sam Loyd

User:DreamGuy's deletion of the image was unconstructive and pointless, but there could be more about the unsolvable 15-14 variant, which kind of launched the 15 puzzle into a certain renewed notoriety for a few years in the 1890s(? not sure about the exact dates). AnonMoos (talk) 06:46, 17 March 2011 (UTC)

Obviously, I agree with that as I originally reverted DreamGuy. The diagram makes clear what the configuration of the whole puzzle is for the unsolvable state. It is, of course, possible to swap the 14 and 15 tiles on a solvable puzzle if the state of the rest of the puzzle is freely choosable. As for writing more on the renewal of the craze, I suggest getting a copy of Jerry Slocum's book which is the main source for this. User:Spinningspark 07:48, 17 March 2011 (UTC)

Having the same image as at the top of the article but with numbers flipped serves no encyclopedic purpose whatsoever. It makes the article look amateurish, and it suggests that our readers are too stupid to understand simple English. DreamGuy (talk) 13:11, 17 March 2011 (UTC)

Unfortunately for you, the "minor revision" is the difference between the original solvable puzzle vs. the revised unsolvable puzzle, and also the difference between the original ca. 1880 craze (which burned out fairly quickly) vs. the later ca. 1890s partial revival of interest in it... AnonMoos (talk) 16:05, 17 March 2011 (UTC)

Sources

The book The 15 Puzzle, Jerry Slocum & Dic Sonneveld, ISBN 1-890980-15-3 is cited four times. It is published by the Slocum Puzzle Foundation, which was founded by one of the authors. It seems to be effectively self-published — is this a reliable source? Deltahedron (talk) 18:15, 3 December 2012 (UTC)

The source NeverEndingBooks appears to be a blog [2]. Why is this a reliable source? Deltahedron (talk) 19:49, 3 December 2012 (UTC)

The definition of odd and even permutations is missing

The article does not explain what an odd or even permutation is. It also does not reference a definition. But it uses the term more than once. --Ceving (talk) 14:08, 13 February 2013 (UTC)

The first occurrence of the word "permutation" in the article is in the phrase "parity of the permutations", wikilinked to Parity of a permutation. Not all readers may connect "odd/even" to "parity", but all the same I think this is sufficient.--Nø (talk) 14:25, 13 February 2013 (UTC)

[Not sure if I should have corrected the spelling mistake in the previous comment...] Mostly I'm not certain if this section of the Talk page is indirectly addressing the question that I was trying to answer in the article, but... My current understanding is that the board is in one of two states, solvable or unsolvable, and they are symmetric. If you can transform the board to a known unsolvable state (such as the 14 and 15 reversed), then you know it is unsolvable, but my further belief is that all unsolvable boards can be transformed to that same "bad" state. (By definition all of the solvable boards can be transformed to the same solved "good" state.) If this is in the article, then I'm not seeing it clearly. However the article and this discussion leads to the same conjecture regarding all other boards where solvable and unsolvable states exist. (I'm also uncertain, but believe that some boards are always solvable.) Shanen (talk) 12:29, 3 May 2019 (UTC)

So, first off, yes, in the standard 15 puzzle, or any grid, you can get from unsolvable configuration to any other. This just follows from some group theory and the fact that exactly half the configurations are solvable. I don't know what you mean by other boards; do you mean doing it on other graphs? As mentioned in the article, for 2-vertex-connected graphs, with one exception, half the configurations (specifically, the even ones) will be solvable if the graph is 2-colorable, and all configurations will be solvable if it is not. (And then there is that one exceptional graph where 1/6 of them are solvable.) In general, if the fraction of solvable configurations is 1/n, there will be n equivalence classes. So, as mentioned, in the original case, there are two equivalence classes: Solvable and unsolvable, i.e., all unsolvable ones are equivalent. The same holds for any 2-colorable graph other than the exceptional one, which has 6 equivalence classes (one equivalence class of solvable configurations and 5 different equivalence classes of unsolvable configurations). So, hopefully that answers your question. Again, this is all just basic theory of group/groupoid actions. But I mean go ahead and add it if you think it's worth noting! No reason not to be more explicit, after all. Hopefully I've interpreted your question correctly. Sniffnoy (talk) 22:00, 16 May 2019 (UTC)

The parity of a permutation of an order is the evenness or oddness of the number of two-way exchanges required to restore the order. As alluded to in the 1879 Johnson & Story article, the parity of the overall permutation, including the blank square (call it 16), always remains equal to the evenness or oddness of the distance of 16 from the end. From this, as noted in a follow-up of the article, it also follows that any combination of moves that has 16 starting and ending in the same position, even if not at the end, will preserve the parity of the overall configuration; and that these observations apply, yet more generally, to other similar puzzles, regardless of their size or the number of tiles in them, as long as just one tile is blank. — Preceding unsigned comment added by 65.29.226.169 (talk) 18:27, 27 March 2023 (UTC)

Not necessarily square.

There are variants with non-equal dimensions, the proper name for this puzzle is "mn-1 puzzle", though it's not widely used. But mn-1 puzzles can be treated like n^2-1 puzzles with an extra row (i.e. concentrating on the row(s) first) -- 46.173.12.68 (talk) 10:44, 8 October 2013 (UTC)

The classic solution for the n^2-1 puzzle is to create an (n-1)n-1 puzzle by solving the first row and continuing to solve the mn-1 reducing m by 1 each iteration until m=2. 205.142.232.18 (talk) 20:00, 15 May 2019 (UTC)

Solvability still not clear

The 3rd paragraph on Solvability says that "the converse also holds". The converse of what? Right before there was a equivalence with "if and only if" mentioned. So what is the converse? — Preceding unsigned comment added by 87.92.110.254 (talk) 10:15, 26 January 2022 (UTC)

The original wording of that passage is somewhat clearer and more explicit. SpinningSpark 10:58, 26 January 2022 (UTC)

Puzzle in image not solvable

The image of a 15 puzzle shown on article page is NOT SOLVABLE! If folks are ok with this, the caption for that picture should state this puzzle is not solvable. I found a site that describes how to test for solvability: https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/ Following the algorithm on that site, the displayed puzzle is not solvable

This page gives a fairly simple approach to solving a puzzle. Solve the top row, then the left side row, and then do the same for the remaining unsolved puzzle inside the outer puzzle. https://www.wikihow.com/Solve-Slide-Puzzles — Preceding unsigned comment added by Hanksterr7 (talk • contribs) 00:40, 4 October 2022 (UTC)

I agree the puzzle is unsolvable, but a previous attempt to fix it was reverted on Commons. A further problem is that some other language versions are using this as an example of a magic square solution. So fixing the solvability issue by simply swapping two tiles is going to break the magic square. The easiest solution for our article is to break out the corrected image from the history into a new file. Articles using this as an example of a magic square will still have a problem because they are using an unreachable solution. SpinningSpark 18:12, 5 October 2022 (UTC)

I've reverted the image to its original (as uploaded) configuration which was both solveable and a magic square. Let's see if it sticks this time. SpinningSpark 14:02, 6 October 2022 (UTC)