559:
492:
40:
481:
136:
173:(number of rows plus number of columns) of the empty square from the lower right corner. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular, if the empty square is in the lower right corner, then the puzzle is solvable only if the permutation of the remaining pieces is even.
317:
the fewest slides within an additive constant, but there is a polynomial-time constant-factor approximation. For the 15 puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves (there are 17 configurations requiring 80 moves) or 43 multi-tile moves; the 8 Puzzle always can be solved
821:
Volume 55 Issue 6 (December 2008), Article 26, pp. 29-30. "For the 4 × 4 Fifteen Puzzle, there are 17 different states at a depth of 80 moves from an initial state with the blank in the corner, while for the 2 × 8 Fifteen Puzzle there is a unique state at the maximum state of 140 moves from the
535:. Shown one of these, Matthias Rice, who ran a woodworking business in Boston, started manufacturing the puzzle sometime in December 1879 and convinced a "Yankee Notions" fancy goods dealer to sell them under the name of "Gem Puzzle." In late January 1880, Charles Pevey, a dentist in
71:. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the
353:
feasibly using brute-force methods. In 2011, lower bounds of 152 single-tile moves or 41 multi-tile moves had been established, as well as upper bounds of 208 single-tile moves or 109 multi-tile moves. In 2016, the upper bound was improved to 205 single-tile moves.
570:
claimed that he had invented the puzzle. However, Loyd had no connection to the invention or initial popularity of the puzzle. Loyd's first article about the puzzle was published in 1886, and it was not until 1891 that he first claimed to be the inventor.
549:
Chapman applied for a patent on his "Block
Solitaire Puzzle" on February 21, 1880. However, this patent was rejected, likely because it was not sufficiently different from the August 20, 1878 "Puzzle-Blocks" patent (US 207124) granted to Ernest U. Kinsey.
574:
Some later interest was fueled by Loyd's offer of a $ 1,000 prize (equivalent to $ 33,911 in 2023) to anyone who could provide a solution for achieving a particular combination specified by Loyd, namely reversing the 14 and 15, which Loyd called the
844::"Gasser found 9 positions, requiring 80 moves...We have now proved that the hardest 15-puzzle positions require, in fact, 80 moves. We have also discovered two previously unknown positions, requiring exactly 80 moves to be solved."
215:= 2. This means that there are exactly two equivalency classes of mutually accessible arrangements, and that the parity described is the only non-trivial invariant, although equivalent descriptions exist.
621:
263:
components of that vertex. Excluding these cases, Wilson showed that other than one exceptional graph on 7 vertices, it is possible to obtain all permutations unless the graph is
288:
503:, who is said to have shown friends, as early as 1874, a precursor puzzle consisting of 16 numbered blocks that were to be put together in rows of four, each summing to 34 (see
470:
405:
243:. The problem has some degenerate cases where the answer is either trivial or a simple combination of the answers to the same problem on some subgraphs. Namely, for
434:
487:'s unsolvable 15 Puzzle, with tiles 14 and 15 exchanged. This puzzle is not solvable as it would require a change of the invariant to move it to the solved state.
154:
puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a binary function of the tile configuration that is
626:
1348:
723:
1234:
1242:
1049:
1017:
764:
620:
was an expert at solving the 15 puzzle. He had been timed to be able to solve it within 25 seconds; Fischer demonstrated this on
1218:
1182:
967:
158:
under any valid move and then using this to partition the space of all possible labelled states into two mutually inaccessible
1107:
1070:
695:
880:
162:
of the same size. This means that half of all positions are unsolvable, although it says nothing about the remaining half.
1338:
1126:
82:, alluding to its total tile capacity. Similar names are used for different sized variants of the 15 puzzle, such as the
1333:
524:
101:
1328:
104:. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the
367:
558:
614:
536:
512:
710:, SARA 2000. Lecture Notes in Computer Science, vol. 1864, Springer, Berlin, Heidelberg, pp. 45–55,
929:
600:
314:
166:
155:
43:
To solve the puzzle, the numbers must be rearranged into numerical order from left to right, top to bottom.
1135:
660:
832:
1343:
904:
868:
147:
110:
539:, Massachusetts, garnered some attention by offering a cash reward for a solution to the 15 Puzzle.
255:, only the connected component of the vertex with the "empty space" is relevant; and if there is an
1222:
1140:
639:
500:
256:
119:
1063:
The Math Book: From
Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics
606:
Versions of the 15 puzzle include a different number of tiles, such as the 8-puzzle or 24-puzzle.
267:, in which case exactly the even permutations can be obtained. The exceptional graph is a regular
114:. That is, they never overestimate the number of moves left, which ensures optimality for certain
1207:
1161:
670:
655:
508:
322:). The multi-tile metric counts subsequent moves of the empty tile in the same direction as one.
252:
1271:
1238:
1199:
1153:
1103:
1066:
1045:
1013:
719:
439:
378:
260:
222:
159:
94:
1302:
1261:
1191:
1145:
1100:
Adam
Spencer's Big Book of Numbers: Everything you wanted to know about the numbers 1 to 100
794:
711:
491:
383:
226:
170:
115:
105:
1283:
1231:
The Cube: The
Ultimate Guide to the World's Best-Selling Puzzle—Secrets, Stories, Solutions
1173:
953:
941:
30:"Magic 15" redirects here. For the numbered grid where each row and column sums to 15, see
1279:
1169:
410:
264:
665:
350:
1312:
527:
started manufacturing the puzzle. By
December 1879, these were sold both locally and in
753:
729:
68:
799:
782:
1322:
1266:
892:
856:
754:"Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable"
644:
617:
532:
1297:
1083:"Bobby Fischer solves a 15 puzzle in 17 seconds on Carson Tonight Show - 11/08/1972"
978:
916:
596:
504:
236:
31:
702:
108:
between each block and its position in the goal configuration. Note that both are
1252:
Wilson, Richard M. (1974), "Graph puzzles, homotopy, and the alternating group",
78:
Named after the number of tiles in the frame, the 15 puzzle may also be called a
520:
495:
U.S. political cartoon about finding a
Republican presidential candidate in 1880
374:
248:
39:
135:
1308:
Maximal number of moves required for the m X n generalization of the 15 puzzle
1082:
696:"Recent Progress in the Design and Analysis of Admissible Heuristic Functions"
592:
318:
in no more than 31 single-tile moves or 24 multi-tile moves (integer sequence
244:
240:
75:
is to place the tiles in numerical order (from left to right, top to bottom).
17:
1275:
1203:
1157:
814:
511:, by way of Chapman's son, Frank, and from there, via sundry connections, to
1180:
Johnson, Wm. Woolsey; Story, William E. (1879), "Notes on the "15" Puzzle",
715:
480:
97:
647:, an operation on skew Young tableaux similar to the moves of the 15 puzzle
583:, because it requires a transformation from an even to an odd permutation.
567:
516:
484:
363:
1211:
1165:
650:
310:
268:
1089:, 8 November 1972, Johnny Carson Productions, retrieved 1 August 2021.
528:
436:
sliding puzzle with square tiles of equal size can be represented by
72:
1195:
1149:
968:"The Fifteen Puzzle: A Motivating Example for the Alternating Group"
305:
puzzle, finding a solution is easy. But, the problem of finding the
287:
of its permutations can be attained, which gives an instance of the
499:
The puzzle was "invented" by Noyes Palmer
Chapman, a postmaster in
557:
490:
479:
134:
38:
579:. This is impossible, as had been shown over a decade earlier by
1124:
Archer, Aaron F. (1999), "A modern treatment of the 15 puzzle",
377:, it can be proved that the 15 puzzle can be represented by the
543:
373:
Because the combinations of the 15 puzzle can be generated by
150:
argument to show that half of the starting positions for the
1307:
319:
562:
Sam Loyd's 1914 illustration of the unsolvable variation.
271:
with one diagonal and a vertex at the center added; only
235:
studied the generalization of the 15 puzzle to arbitrary
259:, the problem reduces to the same puzzle on each of the
831:
A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt,
507:). Copies of the improved 15 puzzle made their way to
366:(not a group, as not all moves can be composed); this
442:
413:
386:
325:
The number of possible positions of the 24 puzzle is
195:
are both larger or equal to 2, all even permutations
1005:
1003:
1001:
999:
833:
The parallel search bench ZRAM and its applications
783:"The (n−1)-puzzle and related relocation problems"
464:
428:
399:
977:. East Tennessee State University. Archived from
603:puzzle with similar operations to the 15 Puzzle.
1028:
857:"The Fifteen Puzzle can be solved in 43 "moves""
27:Sliding puzzle with fifteen pieces and one space
917:"5x5 sliding puzzle can be solved in 205 moves"
239:, the original problem being the case of a 4×4
761:National Conference on Artificial Intelligence
1044:, pp.10-12, Cambridge University Press, 1994
1012:, by Jerry Slocum & Dic Sonneveld, 2006.
704:Abstraction, Reformulation, and Approximation
251:, the puzzle has no freedom; if the graph is
8:
852:
850:
815:Linear-time disk-based implicit graph search
580:
362:The transformations of the 15 puzzle form a
176:
143:
689:
687:
685:
199:solvable. It can be proven by induction on
1265:
1254:Journal of Combinatorial Theory, Series B
1229:Slocum, Jerry; Singmaster, David (2009).
1139:
881:"m × n puzzle (current state of the art)"
798:
781:Ratner, Daniel; Warmuth, Manfred (1990).
752:Ratner, Daniel; Warmuth, Manfred (1986).
447:
441:
412:
391:
385:
169:of all 16 squares plus the parity of the
1217:Edward Kasner & James Newman (1940)
701:, in Choueiry, B. Y.; Walsh, T. (eds.),
681:
627:The Tonight Show Starring Johnny Carson
232:
221:gave another proof, based on defining
218:
1315:with download (from Herbert Kociemba)
7:
1065:, p. 262, Sterling Publishing, 2009
566:From 1891 until his death in 1911,
179:also showed that on boards of size
93:puzzle is a classical problem for
86:which has 8 tiles in a 3×3 frame.
25:
1127:The American Mathematical Monthly
349:, which is too many to calculate
869:"24 puzzle new lower bound: 152"
770:from the original on 2012-03-09.
1219:Mathematics and the Imagination
1183:American Journal of Mathematics
787:Journal of Symbolic Computation
930:Puzzles, Groups, and Groupoids
905:"5x5 can be solved in 109 MTM"
1:
1029:Slocum & Singmaster (2009
883:. Sliding Tile Puzzle Corner.
837:Annals of Operations Research
800:10.1016/S0747-7171(08)80001-6
1349:19th-century fads and trends
1298:The history of the 15 puzzle
1267:10.1016/0095-8956(74)90098-7
525:American School for the Deaf
919:. Domain of the Cube Forum.
907:. Domain of the Cube Forum.
895:. Domain of the Cube Forum.
301:For larger versions of the
1365:
1102:, p. 58, Brio Books, 2014
954:The 15-puzzle groupoid (2)
942:The 15-puzzle groupoid (1)
871:. Domain of the Cube Forum
859:. Domain of the Cube Forum
587:Varieties of the 15 puzzle
581:Johnson & Story (1879)
177:Johnson & Story (1879)
144:Johnson & Story (1879)
29:
1235:Black Dog & Leventhal
167:parity of the permutation
1313:15-Puzzle Optimal Solver
932:, The Everything Seminar
523:, where students in the
513:Watch Hill, Rhode Island
465:{\displaystyle A_{2k-1}}
313:. It is also NP-hard to
1303:Fifteen Puzzle Solution
716:10.1007/3-540-44914-0_3
1061:Clifford A. Pickover,
661:Pebble motion problems
595:, manufactured in the
563:
496:
488:
466:
430:
401:
400:{\displaystyle A_{15}}
140:
44:
561:
546:in the U.S. in 1880.
494:
483:
467:
431:
402:
289:exotic embedding of S
165:The invariant is the
138:
42:
1339:NP-complete problems
1223:Simon & Schuster
1042:Puzzles for Pleasure
956:, Never Ending Books
944:, Never Ending Books
694:Korf, R. E. (2000),
615:Chess world champion
440:
429:{\displaystyle 2k-1}
411:
384:
1334:Combination puzzles
1221:, pp 177–80,
640:Combination puzzles
501:Canastota, New York
370:on configurations.
257:articulation vertex
223:equivalence classes
160:equivalence classes
1329:Mechanical puzzles
842:(1999), pp. 45–63.
819:Journal of the ACM
671:Three cups problem
656:Mechanical puzzles
564:
542:The game became a
509:Syracuse, New York
497:
489:
462:
426:
397:
141:
139:A solved 15 Puzzle
45:
1040:Barry R. Clarke,
984:on 7 January 2021
975:faculty.etsu.edu/
813:Richard E. Korf,
725:978-3-540-67839-7
515:, and finally to
379:alternating group
116:search algorithms
106:taxicab distances
16:(Redirected from
1356:
1286:
1269:
1248:
1214:
1176:
1143:
1111:
1096:
1090:
1087:The Tonight Show
1080:
1074:
1059:
1053:
1038:
1032:
1026:
1020:
1007:
994:
993:
991:
989:
983:
972:
966:Beeler, Robert.
963:
957:
951:
945:
939:
933:
928:Jim Belk (2008)
926:
920:
914:
908:
902:
896:
890:
884:
878:
872:
866:
860:
854:
845:
829:
823:
811:
805:
804:
802:
778:
772:
771:
769:
758:
749:
743:
742:
741:
740:
734:
728:, archived from
709:
700:
691:
622:November 8, 1972
471:
469:
468:
463:
461:
460:
435:
433:
432:
427:
406:
404:
403:
398:
396:
395:
348:
346:
340:
338:
337:
334:
331:
286:
284:
283:
280:
277:
227:Hamiltonian path
207:, starting with
171:taxicab distance
21:
1364:
1363:
1359:
1358:
1357:
1355:
1354:
1353:
1319:
1318:
1294:
1289:
1251:
1245:
1228:
1196:10.2307/2369492
1179:
1150:10.2307/2589612
1123:
1119:
1114:
1097:
1093:
1081:
1077:
1060:
1056:
1039:
1035:
1027:
1023:
1008:
997:
987:
985:
981:
970:
965:
964:
960:
952:
948:
940:
936:
927:
923:
915:
911:
903:
899:
891:
887:
879:
875:
867:
863:
855:
848:
843:
830:
826:
822:initial state."
812:
808:
780:
779:
775:
767:
756:
751:
750:
746:
738:
736:
732:
726:
707:
698:
693:
692:
683:
679:
636:
612:
589:
556:
478:
443:
438:
437:
409:
408:
407:. In fact, any
387:
382:
381:
360:
344:
342:
335:
332:
329:
328:
326:
296:
292:
281:
278:
275:
274:
272:
133:
128:
67:and more) is a
61:Game of Fifteen
35:
28:
23:
22:
15:
12:
11:
5:
1362:
1360:
1352:
1351:
1346:
1341:
1336:
1331:
1321:
1320:
1317:
1316:
1310:
1305:
1300:
1293:
1292:External links
1290:
1288:
1287:
1249:
1244:978-1579128050
1243:
1226:
1215:
1190:(4): 397–404,
1177:
1141:10.1.1.19.1491
1134:(9): 793–799,
1120:
1118:
1115:
1113:
1112:
1098:Adam Spencer,
1091:
1075:
1054:
1033:
1021:
995:
958:
946:
934:
921:
909:
897:
893:"208s for 5x5"
885:
873:
861:
846:
824:
806:
793:(2): 111–137.
773:
744:
724:
680:
678:
675:
674:
673:
668:
663:
658:
653:
648:
642:
635:
632:
611:
608:
588:
585:
555:
552:
477:
474:
459:
456:
453:
450:
446:
425:
422:
419:
416:
394:
390:
359:
356:
294:
290:
132:
129:
127:
124:
69:sliding puzzle
26:
24:
18:Fifteen puzzle
14:
13:
10:
9:
6:
4:
3:
2:
1361:
1350:
1347:
1345:
1342:
1340:
1337:
1335:
1332:
1330:
1327:
1326:
1324:
1314:
1311:
1309:
1306:
1304:
1301:
1299:
1296:
1295:
1291:
1285:
1281:
1277:
1273:
1268:
1263:
1259:
1255:
1250:
1246:
1240:
1236:
1232:
1227:
1224:
1220:
1216:
1213:
1209:
1205:
1201:
1197:
1193:
1189:
1185:
1184:
1178:
1175:
1171:
1167:
1163:
1159:
1155:
1151:
1147:
1142:
1137:
1133:
1129:
1128:
1122:
1121:
1116:
1109:
1105:
1101:
1095:
1092:
1088:
1084:
1079:
1076:
1072:
1068:
1064:
1058:
1055:
1051:
1050:0-521-46634-2
1047:
1043:
1037:
1034:
1031:, p. 15)
1030:
1025:
1022:
1019:
1018:1-890980-15-3
1015:
1011:
1010:The 15 Puzzle
1006:
1004:
1002:
1000:
996:
980:
976:
969:
962:
959:
955:
950:
947:
943:
938:
935:
931:
925:
922:
918:
913:
910:
906:
901:
898:
894:
889:
886:
882:
877:
874:
870:
865:
862:
858:
853:
851:
847:
841:
838:
834:
828:
825:
820:
816:
810:
807:
801:
796:
792:
788:
784:
777:
774:
766:
762:
755:
748:
745:
735:on 2010-08-16
731:
727:
721:
717:
713:
706:
705:
697:
690:
688:
686:
682:
676:
672:
669:
667:
664:
662:
659:
657:
654:
652:
649:
646:
645:Jeu de taquin
643:
641:
638:
637:
633:
631:
629:
628:
623:
619:
618:Bobby Fischer
616:
609:
607:
604:
602:
598:
594:
586:
584:
582:
578:
572:
569:
560:
553:
551:
547:
545:
540:
538:
534:
533:Massachusetts
530:
526:
522:
518:
514:
510:
506:
502:
493:
486:
482:
475:
473:
457:
454:
451:
448:
444:
423:
420:
417:
414:
392:
388:
380:
376:
371:
369:
368:groupoid acts
365:
357:
355:
352:
323:
321:
316:
312:
308:
304:
299:
297:
270:
266:
262:
258:
254:
250:
246:
242:
238:
237:finite graphs
234:
233:Wilson (1974)
230:
228:
224:
220:
219:Archer (1999)
216:
214:
210:
206:
202:
198:
194:
190:
186:
182:
178:
174:
172:
168:
163:
161:
157:
153:
149:
145:
137:
130:
125:
123:
121:
117:
113:
112:
107:
103:
99:
96:
92:
87:
85:
81:
76:
74:
70:
66:
65:Mystic Square
62:
58:
54:
51:(also called
50:
41:
37:
33:
19:
1344:Permutations
1257:
1253:
1230:
1187:
1181:
1131:
1125:
1099:
1094:
1086:
1078:
1062:
1057:
1041:
1036:
1024:
1009:
986:. Retrieved
979:the original
974:
961:
949:
937:
924:
912:
900:
888:
876:
864:
839:
836:
827:
818:
809:
790:
786:
776:
760:
747:
737:, retrieved
730:the original
703:
666:Rubik's Cube
625:
613:
605:
590:
577:14-15 puzzle
576:
573:
565:
548:
541:
505:magic square
498:
372:
361:
358:Group theory
351:God's number
324:
309:solution is
306:
302:
300:
253:disconnected
231:
217:
212:
208:
204:
200:
196:
192:
188:
184:
180:
175:
164:
151:
142:
109:
90:
88:
83:
79:
77:
64:
60:
56:
52:
48:
46:
36:
32:Magic square
988:26 December
610:Pop culture
521:Connecticut
315:approximate
261:biconnected
131:Solvability
126:Mathematics
80:"16 puzzle"
57:Boss Puzzle
1323:Categories
1117:References
1108:192113433X
1071:1402757964
739:2010-04-26
593:Minus Cube
241:grid graph
111:admissible
102:heuristics
100:involving
98:algorithms
53:Gem Puzzle
1276:0095-8956
1260:: 86–96,
1204:0002-9327
1158:0002-9890
1136:CiteSeerX
537:Worcester
455:−
421:−
265:bipartite
156:invariant
84:8 puzzle,
49:15 puzzle
765:Archived
634:See also
568:Sam Loyd
554:Sam Loyd
517:Hartford
485:Sam Loyd
375:3-cycles
364:groupoid
307:shortest
249:polygons
187:, where
118:such as
95:modeling
1284:0332555
1212:2369492
1174:1732661
1166:2589612
651:Klotski
599:, is a
476:History
339:
327:
320:A087725
311:NP-hard
285:
273:
269:hexagon
146:used a
1282:
1274:
1241:
1210:
1202:
1172:
1164:
1156:
1138:
1106:
1069:
1048:
1016:
722:
529:Boston
293:into S
225:via a
148:parity
73:puzzle
1208:JSTOR
1162:JSTOR
982:(PDF)
971:(PDF)
768:(PDF)
757:(PDF)
733:(PDF)
708:(PDF)
699:(PDF)
677:Notes
624:, on
544:craze
245:paths
1272:ISSN
1239:ISBN
1200:ISSN
1154:ISSN
1104:ISBN
1067:ISBN
1046:ISBN
1014:ISBN
990:2020
720:ISBN
597:USSR
591:The
343:7.76
247:and
203:and
191:and
89:The
47:The
1262:doi
1192:doi
1146:doi
1132:106
795:doi
712:doi
330:25!
197:are
1325::
1280:MR
1278:,
1270:,
1258:16
1256:,
1237:.
1233:.
1206:,
1198:,
1186:,
1170:MR
1168:,
1160:,
1152:,
1144:,
1130:,
1085:,
998:^
973:.
849:^
840:90
835:,
817:,
791:10
789:.
785:.
763:.
759:.
718:,
684:^
630:.
601:3D
531:,
519:,
472:.
393:15
347:10
341:≈
298:.
229:.
211:=
183:×
122:.
120:A*
63:,
59:,
55:,
1264::
1247:.
1225:.
1194::
1188:2
1148::
1110:.
1073:.
1052:.
992:.
803:.
797::
714::
458:1
452:k
449:2
445:A
424:1
418:k
415:2
389:A
345:×
336:2
333:/
303:n
295:6
291:5
282:6
279:/
276:1
213:n
209:m
205:n
201:m
193:n
189:m
185:n
181:m
152:n
91:n
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
