Knowledge

God's algorithm

Source 📝

240: 275:. Both these games have a rapidly increasing number of positions with each move. The total number of all possible positions, approximately 5×10 for chess and 10 (on a 19×19 board) for Go, is much too large to allow a brute force solution with current computing technology (compare the now solved, with great difficulty, Rubik's Cube at only about 62:
number of "configurations", with a relatively small, well-defined arsenal of "moves" that may be applicable to configurations and then lead to a new configuration. Solving the puzzle means to reach a designated "final configuration", a singular configuration, or one of a collection of configurations.
291:
Even this strategy is not possible with Go. Besides having hugely more positions to evaluate, no one so far has successfully constructed a set of simple rules for evaluating the strength of a Go position as has been done for chess, though neural networks trained through reinforcement learning can
247:
An algorithm to determine the minimum number of moves to solve Rubik's Cube was published in 1997 by Richard Korf. While it had been known since 1995 that 20 was a lower bound on the number of moves for the solution in the worst case, Tom Rokicki proved in 2010 that no configuration requires more
98:
Instead of asking for a full solution, one can equivalently ask for a single move from an initial but not final configuration, where the move is the first of some optimal solution. An algorithm for the single-move version of the problem can be turned into an algorithm for the original problem by
292:
provide evaluations of a position that exceed human ability. Evaluation algorithms are prone to make elementary mistakes so even for a limited look ahead with the goal limited to finding the strongest interim position, a God's algorithm has not been possible for Go.
303:
proved this to be so by calculating a database of all positions with ten or fewer pieces, providing a God's algorithm for all end games of draughts which was used to prove that all perfectly played games of draughts end in a draw. However, draughts with only
283:
positions). Consequently, a brute force determination of God's algorithm for these games is not possible. While chess computers have been built that are capable of beating even the best human players, they do not calculate the game all the way to the end.
75:
the puzzle is solvable from that initial configuration, otherwise it signals the impossibility of a solution). A solution is optimal if the sequence of moves is as short as possible. The highest value of this, among all initial configurations, is known as
323:
The magnitude of the set of positions of a puzzle does not entirely determine whether a God's algorithm is possible. The already solved Tower of Hanoi puzzle can have an arbitrary number of pieces, and the number of positions increases exponentially as
103:
while applying each move reported to the present configuration, until a final one is reached; conversely, any algorithm for the original problem can be turned into an algorithm for the single-move version by truncating its output to its first move.
288:, for instance, searched only 11 moves ahead (counting a move by each player as two moves), reducing the search space to only 10. After this, it assessed each position for advantage according to rules derived from human play and experience. 239: 267:
Some well known games with a very limited set of simple well-defined rules and moves have nevertheless never had their God's algorithm for a winning strategy determined. Examples are the board games
71:
An algorithm can be considered to solve such a puzzle if it takes as input an arbitrary initial configuration and produces as output a sequence of moves leading to a final configuration (
461:), p. 207: "...the Pyraminx is much simpler than the Magic Cube... Nicholas Hammond has shown that God's Algorithm is at most 21 moves (including the four trivial vertex moves). " 221: 376: 349: 583: 996: 890:
Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi; Kishimoto, Akihiro; Müller, Martin; Lake, Robert; Lu, Paul; Sutphen, Steve (14 September 2007).
37:. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the deity is based on the notion that an 1700: 1694: 1612: 965: 234: 1374: 1369: 1364: 1359: 1065: 188:
puzzle, a God's algorithm is known for any given number of disks. The number of moves increases exponentially with the number of disks
95:
indexed by initial configurations would allow solutions to be found very quickly, but would require an extraordinary amount of memory.
1679: 137: 87:
Some writers, such as David Joyner, consider that for an algorithm to be properly referred to as "God's algorithm", it should also be
950: 850: 458: 1410: 1483: 84:
value. God's algorithm, then, for a given puzzle, is an algorithm that solves the puzzle and produces only optimal solutions.
883: 868: 823: 808: 437: 1034: 989: 1463: 145: 1731: 1721: 1508: 285: 91:, meaning that the algorithm does not require extraordinary amounts of memory or time. For example, using a giant 891: 1736: 1468: 982: 599: 1685: 814:
Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., "Artificial-life, agents and Go", in Mohammadian, Masoud,
168:
can be solved in 80 single-tile moves or 43 multi-tile moves in the worst case. For its generalization the
1726: 1663: 1538: 1498: 351:. Nevertheless, the solution algorithm is applicable to any size problem, with a running time scaling as 100: 511: 453:
by Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx, and Tamás Vekerdy (1987, Oxford University Press,
299:(checkers) has long been suspected of being "played out" by its expert practitioners. In 2007 Schaeffer 1642: 1390: 1310: 63:
To solve the puzzle a sequence of moves is applied, starting from some arbitrary initial configuration.
1647: 1417: 405: 906: 399: 1300: 1085: 249: 1493: 1292: 1060: 1044: 960:, held in Berkeley, California, 10–16 August 1980, pp. 307–312, Birkhauser Boston Inc, 1983 561: 141: 1448: 1427: 1080: 1563: 1336: 1166: 1039: 961: 946: 930: 922: 879: 864: 846: 819: 804: 454: 433: 113: 34: 193: 1523: 1458: 1422: 1405: 1400: 1254: 1128: 1024: 914: 256: 354: 327: 1528: 1453: 1151: 185: 1075: 1005: 320:, in the database, is a much easier problem to solve –of the same order as Rubik's cube. 117: 23: 910: 430:
Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions
1602: 1548: 1395: 1259: 1029: 839: 621: 387: 165: 121: 565: 1715: 1533: 1231: 1123: 1019: 566:"Finding a shortest solution for the N × N extension of the 15-puzzle is intractable" 532: 129: 27: 1553: 1473: 1241: 1203: 133: 92: 472: 1607: 1586: 1518: 1513: 1443: 1277: 1269: 1208: 1190: 1133: 1070: 674: 410: 392: 252: 1223: 1213: 59: 38: 926: 638:
Rokicki, Tomas; Kociemba, Herbert; Davidson, Morley; Dethridge, John (2010).
1637: 1543: 1503: 1171: 1161: 1118: 918: 591: 272: 148:, in which the configurations are the vertices, and the moves are the arcs. 125: 934: 958:
Proceedings of the Fourth International Congress on Mathematical Education
956:
Singmaster, David, "The educational value of the Hungarian 'Magic Cube'",
1558: 1488: 1478: 1318: 1249: 1198: 1100: 1095: 1090: 595: 572:. National Conference on Artificial Intelligence, 1986. pp. 168–172. 476: 296: 974: 173: 1328: 679: 55: 30: 176:, so it is not known whether there is a practical God's algorithm. 16:
Algorithm for solving a puzzle or game in the fewest possible moves
1282: 1156: 268: 238: 622:
Finding optimal solutions to Rubik's Cube using pattern databases
816:
New Frontiers in Computational Intelligence and its Applications
978: 41:
being would know an optimal step from any given configuration.
22:
is a notion originating in discussions of ways to solve the
628:(AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700–705. 756:
Moore & Mertens, chapter 1.3, "Playing chess with God"
639: 473:"Rubik's Cube quest for speedy solution comes to an end" 510:
A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt,
259:
had "rashly conjectured" this number to be 20 in 1980.
172:-puzzle, the problem of finding an optimal solution is 531:
Norskog, Bruce; Davidson, Morley (December 8, 2010).
357: 330: 196: 1672: 1656: 1625: 1595: 1579: 1572: 1436: 1383: 1350: 1327: 1309: 1291: 1268: 1240: 1222: 1189: 1180: 1142: 1109: 1053: 1012: 584:"An optimal solution to the Towers of Hanoi Puzzle" 512:
The parallel search bench ZRAM and its applications
838: 370: 343: 255:on the length of optimal solutions. Mathematician 215: 112:Well-known puzzles fitting this description are 876:Catalysis, God's Algorithm, and the Green Demon 26:puzzle, but which can also be applied to other 990: 8: 626:Proc. Natl. Conf. on Artificial Intelligence 1576: 1186: 997: 983: 975: 778:Moore & Mertens, "Notes" to chapter 1 488: 486: 362: 356: 335: 329: 201: 195: 533:"The Fifteen Puzzle can be solved in 43 140:. These have in common that they can be 421: 859:Moore, Cristopher; Mertens, Stephan, 829:Fraser, Rober (ed); Hannah, W. (ed), 7: 1701:1982 World Rubik's Cube Championship 831:The Draught Players' Weekly Magazine 818:, pp. 125–139, IOS Press, 2000 1695:The Simple Solution to Rubik's Cube 878:, Amsterdam University Press, 2009 833:, vol. 2, Glasgow: J H Berry, 1885. 471:Jonathan Fildes (August 11, 2010). 845:. Johns Hopkins University Press. 588:Universidad Autónoma de Manizales 235:Optimal solutions for Rubik's Cube 138:missionaries and cannibals problem 14: 1066:Rubik's family cubes of all sizes 132:is also covered, as well as many 863:, Oxford University Press, 2011 1680:Rubik's Cube in popular culture 1: 582:Rueda, Carlos (August 2000). 516:Annals of Operations Research 248:than 20 moves. Thus, 20 is a 943:Notes on Rubik's Magic Cube 747:Fraser & Hannah, p. 197 1753: 1643:Thistlethwaite's algorithm 841:Adventures in Group Theory 312:positions and even fewer, 232: 861:The Nature of Computation 128:. The one-person game of 80:, or, more formally, the 1086:5×5×5 (Professor's Cube) 675:"Chess Position Ranking" 541:Domain of the Cube Forum 492:Singmaster, p. 311, 1980 451:Rubik's Cubic Compendium 243:A scrambled Rubik's Cube 1686:Rubik, the Amazing Cube 1081:4×4×4 (Rubik's Revenge) 919:10.1126/science.1144079 216:{\displaystyle 2^{n}-1} 1664:World Cube Association 1539:Anthony Michael Brooks 1499:Krishnam Raju Gadiraju 837:Joyner, David (2002). 372: 345: 244: 217: 142:modeled mathematically 101:invoking it repeatedly 54:The notion applies to 1657:Official organization 1311:Truncated icosahedron 373: 371:{\displaystyle 2^{n}} 346: 344:{\displaystyle 3^{n}} 242: 218: 1076:3×3×3 (Rubik's Cube) 892:"Checkers Is Solved" 640:"God's Number is 20" 432:, Hachette UK, 2014 428:Paul Anthony Jones, 400:Proofs from THE BOOK 355: 328: 228: 194: 1351:Virtual combination 1183:combination puzzles 1145:combination puzzles 1071:2×2×2 (Pocket Cube) 941:Singmaster, David, 911:2007Sci...317.1518S 905:(5844): 1518–1522. 570:Proceedings AAAI-86 295:On the other hand, 1732:Mathematical games 1648:Rubik's Cube group 1494:Prithveesh K. Bhat 1418:Rubik's Revolution 1293:Great dodecahedron 1045:Oskar van Deventer 874:Rothenberg, Gadi, 803:, MIT Press, 2004 726:Mohammadian, p. 11 620:Richard E. Korf, " 562:Manfred K. Warmuth 521:(1999), pp. 45–63. 406:Rubik's Cube group 368: 341: 245: 213: 152:Mechanical puzzles 114:mechanical puzzles 58:that can assume a 35:mathematical games 1722:Search algorithms 1709: 1708: 1621: 1620: 1346: 1345: 1110:Variations of the 1040:Panagiotis Verdes 966:978-0-8176-3082-9 663:Rothenberg, p. 11 1744: 1673:Related articles 1577: 1524:David Singmaster 1484:Shotaro Makisumi 1459:Jessica Fridrich 1437:Renowned solvers 1353:puzzles (>3D) 1301:Alexander's Star 1255:Pyraminx Crystal 1187: 1129:Nine-Colour Cube 1101:8×8×8 (V-Cube 8) 1096:7×7×7 (V-Cube 7) 1091:6×6×6 (V-Cube 6) 1013:Puzzle inventors 999: 992: 985: 976: 945:, Penguin, 1981 938: 896: 856: 844: 801:What is Thought? 788: 785: 779: 776: 770: 763: 757: 754: 748: 745: 739: 736: 730: 718: 712: 709: 703: 702:Singmaster, 1981 700: 694: 691: 685: 684: 670: 664: 661: 655: 654: 652: 650: 635: 629: 618: 612: 611: 609: 607: 598:. Archived from 579: 573: 558: 552: 551: 549: 547: 528: 522: 508: 502: 501:Joyner, page 149 499: 493: 490: 481: 480: 468: 462: 447: 441: 426: 377: 375: 374: 369: 367: 366: 350: 348: 347: 342: 340: 339: 319: 317: 311: 309: 282: 280: 257:David Singmaster 224: 222: 220: 219: 214: 206: 205: 1752: 1751: 1747: 1746: 1745: 1743: 1742: 1741: 1712: 1711: 1710: 1705: 1668: 1652: 1633:God's algorithm 1617: 1591: 1568: 1529:Ron van Bruchem 1454:Bob Burton, Jr. 1449:Édouard Chambon 1432: 1428:Rubik's Triamid 1379: 1352: 1342: 1323: 1305: 1287: 1264: 1236: 1218: 1182: 1176: 1152:Helicopter Cube 1144: 1138: 1111: 1105: 1049: 1008: 1003: 972: 894: 889: 853: 836: 799:Baum, Eric B., 796: 791: 786: 782: 777: 773: 764: 760: 755: 751: 746: 742: 737: 733: 729: 719: 715: 710: 706: 701: 697: 692: 688: 672: 671: 667: 662: 658: 648: 646: 637: 636: 632: 619: 615: 605: 603: 581: 580: 576: 560:Daniel Ratner, 559: 555: 545: 543: 530: 529: 525: 509: 505: 500: 496: 491: 484: 470: 469: 465: 448: 444: 427: 423: 419: 384: 358: 353: 352: 331: 326: 325: 315: 313: 307: 305: 278: 276: 265: 237: 231: 197: 192: 191: 189: 186:Towers of Hanoi 182: 180:Towers of Hanoi 162: 154: 110: 69: 52: 47: 20:God's algorithm 17: 12: 11: 5: 1750: 1748: 1740: 1739: 1734: 1729: 1724: 1714: 1713: 1707: 1706: 1704: 1703: 1698: 1691: 1690: 1689: 1676: 1674: 1670: 1669: 1667: 1666: 1660: 1658: 1654: 1653: 1651: 1650: 1645: 1640: 1635: 1629: 1627: 1623: 1622: 1619: 1618: 1616: 1615: 1610: 1605: 1603:Layer by Layer 1599: 1597: 1593: 1592: 1590: 1589: 1583: 1581: 1574: 1570: 1569: 1567: 1566: 1561: 1556: 1551: 1549:Feliks Zemdegs 1546: 1541: 1536: 1531: 1526: 1521: 1516: 1511: 1506: 1501: 1496: 1491: 1486: 1481: 1476: 1471: 1466: 1464:Chris Hardwick 1461: 1456: 1451: 1446: 1440: 1438: 1434: 1433: 1431: 1430: 1425: 1420: 1415: 1414: 1413: 1411:Master Edition 1403: 1398: 1393: 1387: 1385: 1381: 1380: 1378: 1377: 1375:Magic 120-cell 1372: 1367: 1362: 1356: 1354: 1348: 1347: 1344: 1343: 1341: 1340: 1337:Rubik's Domino 1333: 1331: 1325: 1324: 1322: 1321: 1315: 1313: 1307: 1306: 1304: 1303: 1297: 1295: 1289: 1288: 1286: 1285: 1280: 1274: 1272: 1266: 1265: 1263: 1262: 1260:Skewb Ultimate 1257: 1252: 1246: 1244: 1238: 1237: 1235: 1234: 1228: 1226: 1220: 1219: 1217: 1216: 1211: 1206: 1201: 1195: 1193: 1184: 1178: 1177: 1175: 1174: 1169: 1164: 1159: 1154: 1148: 1146: 1140: 1139: 1137: 1136: 1131: 1126: 1121: 1115: 1113: 1107: 1106: 1104: 1103: 1098: 1093: 1088: 1083: 1078: 1073: 1068: 1063: 1057: 1055: 1051: 1050: 1048: 1047: 1042: 1037: 1032: 1027: 1022: 1016: 1014: 1010: 1009: 1004: 1002: 1001: 994: 987: 979: 970: 969: 954: 939: 887: 872: 857: 851: 834: 827: 812: 795: 792: 790: 789: 780: 771: 758: 749: 740: 731: 728: 727: 724: 720: 713: 704: 695: 686: 665: 656: 630: 613: 574: 553: 523: 503: 494: 482: 463: 442: 420: 418: 415: 414: 413: 408: 403: 396: 390: 388:Oracle machine 383: 380: 365: 361: 338: 334: 264: 263:Unsolved games 261: 233:Main article: 230: 227: 212: 209: 204: 200: 181: 178: 166:Fifteen puzzle 161: 155: 153: 150: 146:directed graph 136:, such as the 122:Tower of Hanoi 109: 106: 68: 65: 51: 48: 46: 43: 15: 13: 10: 9: 6: 4: 3: 2: 1749: 1738: 1735: 1733: 1730: 1728: 1727:Logic puzzles 1725: 1723: 1720: 1719: 1717: 1702: 1699: 1697: 1696: 1692: 1688: 1687: 1683: 1682: 1681: 1678: 1677: 1675: 1671: 1665: 1662: 1661: 1659: 1655: 1649: 1646: 1644: 1641: 1639: 1636: 1634: 1631: 1630: 1628: 1624: 1614: 1611: 1609: 1606: 1604: 1601: 1600: 1598: 1594: 1588: 1585: 1584: 1582: 1578: 1575: 1571: 1565: 1562: 1560: 1557: 1555: 1552: 1550: 1547: 1545: 1542: 1540: 1537: 1535: 1534:Eric Limeback 1532: 1530: 1527: 1525: 1522: 1520: 1517: 1515: 1512: 1510: 1507: 1505: 1502: 1500: 1497: 1495: 1492: 1490: 1487: 1485: 1482: 1480: 1477: 1475: 1472: 1470: 1467: 1465: 1462: 1460: 1457: 1455: 1452: 1450: 1447: 1445: 1442: 1441: 1439: 1435: 1429: 1426: 1424: 1423:Rubik's Snake 1421: 1419: 1416: 1412: 1409: 1408: 1407: 1406:Rubik's Magic 1404: 1402: 1401:Rubik's Clock 1399: 1397: 1394: 1392: 1389: 1388: 1386: 1382: 1376: 1373: 1371: 1368: 1366: 1363: 1361: 1358: 1357: 1355: 1349: 1338: 1335: 1334: 1332: 1330: 1326: 1320: 1317: 1316: 1314: 1312: 1308: 1302: 1299: 1298: 1296: 1294: 1290: 1284: 1281: 1279: 1276: 1275: 1273: 1271: 1267: 1261: 1258: 1256: 1253: 1251: 1248: 1247: 1245: 1243: 1239: 1233: 1232:Skewb Diamond 1230: 1229: 1227: 1225: 1221: 1215: 1212: 1210: 1207: 1205: 1202: 1200: 1197: 1196: 1194: 1192: 1188: 1185: 1179: 1173: 1170: 1168: 1165: 1163: 1160: 1158: 1155: 1153: 1150: 1149: 1147: 1141: 1135: 1132: 1130: 1127: 1125: 1122: 1120: 1117: 1116: 1114: 1108: 1102: 1099: 1097: 1094: 1092: 1089: 1087: 1084: 1082: 1079: 1077: 1074: 1072: 1069: 1067: 1064: 1062: 1059: 1058: 1056: 1054:Rubik's Cubes 1052: 1046: 1043: 1041: 1038: 1036: 1033: 1031: 1028: 1026: 1025:Larry Nichols 1023: 1021: 1018: 1017: 1015: 1011: 1007: 1000: 995: 993: 988: 986: 981: 980: 977: 973: 967: 963: 959: 955: 952: 951:0-907395-00-7 948: 944: 940: 936: 932: 928: 924: 920: 916: 912: 908: 904: 900: 893: 888: 885: 881: 877: 873: 870: 866: 862: 858: 854: 852:0-8018-6947-1 848: 843: 842: 835: 832: 828: 825: 821: 817: 813: 810: 806: 802: 798: 797: 793: 784: 781: 775: 772: 768: 762: 759: 753: 750: 744: 741: 735: 732: 725: 722: 721: 717: 714: 708: 705: 699: 696: 690: 687: 682: 681: 676: 669: 666: 660: 657: 645: 641: 634: 631: 627: 623: 617: 614: 602:on 2004-06-05 601: 597: 593: 589: 585: 578: 575: 571: 567: 563: 557: 554: 542: 538: 536: 527: 524: 520: 517: 513: 507: 504: 498: 495: 489: 487: 483: 478: 474: 467: 464: 460: 459:0-19-853202-4 456: 452: 446: 443: 439: 435: 431: 425: 422: 416: 412: 409: 407: 404: 402: 401: 397: 394: 391: 389: 386: 385: 381: 379: 363: 359: 336: 332: 321: 302: 298: 293: 289: 287: 274: 270: 262: 260: 258: 254: 251: 241: 236: 226: 210: 207: 202: 198: 187: 179: 177: 175: 171: 167: 159: 156: 151: 149: 147: 143: 139: 135: 134:logic puzzles 131: 130:peg solitaire 127: 123: 119: 115: 107: 105: 102: 96: 94: 90: 85: 83: 79: 74: 66: 64: 61: 57: 49: 44: 42: 40: 36: 32: 29: 28:combinatorial 25: 21: 1737:Rubik's Cube 1693: 1684: 1632: 1580:Speedsolving 1554:Collin Burns 1509:Frank Morris 1474:Rowe Hessler 1391:Missing Link 1242:Dodecahedron 1204:Pyraminx Duo 1112:Rubik's Cube 1006:Rubik's Cube 971: 957: 942: 902: 898: 875: 860: 840: 830: 815: 800: 783: 774: 766: 761: 752: 743: 734: 723:Baum, p. 197 716: 711:Baum, p. 188 707: 698: 693:Baum, p. 199 689: 678: 673:John Tromp. 668: 659: 647:. Retrieved 643: 633: 625: 616: 604:. Retrieved 600:the original 587: 577: 569: 556: 544:. Retrieved 540: 534: 526: 518: 515: 506: 497: 466: 450: 445: 429: 424: 398: 395:(game of Go) 322: 300: 294: 290: 266: 246: 229:Rubik's Cube 183: 169: 163: 157: 118:Rubik's Cube 111: 97: 93:lookup table 88: 86: 81: 78:God's number 77: 72: 70: 53: 24:Rubik's Cube 19: 18: 1626:Mathematics 1608:CFOP method 1587:Speedcubing 1564:Mátyás Kuti 1519:Gilles Roux 1514:Lars Petrus 1444:Yu Nakajima 1396:Rubik's 360 1384:Derivatives 1370:MagicCube7D 1365:MagicCube5D 1360:MagicCube4D 1278:Impossiball 1270:Icosahedron 1209:Pyramorphix 1191:Tetrahedron 1143:Other cubic 1134:Sudoku Cube 1035:Tony Fisher 1030:Uwe Mèffert 738:Baum, p.197 411:Solved game 393:Divine move 253:upper bound 1716:Categories 1469:Kevin Hays 1224:Octahedron 1214:BrainTwist 1020:Ernő Rubik 884:9056295896 869:0191620807 824:9051994761 809:0262025485 794:References 765:Schaeffer 644:Cube20.org 438:1472116224 124:, and the 50:Definition 39:omniscient 1638:Superflip 1573:Solutions 1544:Mats Valk 1504:Tyson Mao 1181:Non-cubic 1172:Gear Cube 1162:Dino Cube 1124:Bump Cube 1119:Void Cube 927:0036-8075 769:, p. 1518 649:March 15, 606:March 15, 592:Manizales 546:March 15, 449:See e.g. 286:Deep Blue 208:− 126:15 puzzle 89:practical 1559:Max Park 1489:Toby Mao 1479:Leyan Lo 1319:Tuttminx 1250:Megaminx 1199:Pyraminx 1167:Square 1 1061:Overview 935:17641166 596:Colombia 564:(1986). 477:BBC News 382:See also 297:draughts 184:For the 160:-Puzzles 116:such as 108:Examples 67:Solution 1613:Optimal 1596:Methods 1339:(2x3x3) 907:Bibcode 899:Science 174:NP-hard 82:minimax 56:puzzles 31:puzzles 1329:Cuboid 964:  949:  933:  925:  882:  867:  849:  822:  807:  767:et al. 680:GitHub 457:  436:  301:et al. 120:, the 60:finite 1283:Dogic 1157:Skewb 895:(PDF) 787:Rueda 568:. in 535:moves 417:Notes 269:chess 250:sharp 144:as a 45:Scope 962:ISBN 947:ISBN 931:PMID 923:ISSN 880:ISBN 865:ISBN 847:ISBN 820:ISBN 805:ISBN 651:2022 608:2022 548:2022 455:ISBN 434:ISBN 271:and 164:The 33:and 915:doi 903:317 624:", 314:3.9 277:4.3 1718:: 929:. 921:. 913:. 901:. 897:. 677:. 642:. 594:, 590:. 586:. 539:. 519:90 514:, 485:^ 475:. 378:. 318:10 310:10 281:10 273:Go 225:. 73:if 998:e 991:t 984:v 968:. 953:. 937:. 917:: 909:: 886:. 871:. 855:. 826:. 811:. 683:. 653:. 610:. 550:. 537:" 479:. 440:. 364:n 360:2 337:n 333:3 316:× 308:× 306:5 279:× 223:) 211:1 203:n 199:2 190:( 170:n 158:n

Index

Rubik's Cube
combinatorial
puzzles
mathematical games
omniscient
puzzles
finite
lookup table
invoking it repeatedly
mechanical puzzles
Rubik's Cube
Tower of Hanoi
15 puzzle
peg solitaire
logic puzzles
missionaries and cannibals problem
modeled mathematically
directed graph
Fifteen puzzle
NP-hard
Towers of Hanoi
Optimal solutions for Rubik's Cube

sharp
upper bound
David Singmaster
chess
Go
Deep Blue
draughts

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.