Clever Geek Handbook
📜 ⬆️ ⬇️

Game at 15

Fifteen.jpg
Puzzle Keychain
The word "Fifteen" has other meanings; see Fifteen .

The game of 15 [1] [2] , tag [3] [4] , taken [2] [4] [5] - a popular puzzle , invented in 1878 by Noah Chapman. It is a set of identical square knuckles with printed numbers enclosed in a square box. The length of the side of the box is four times the length of the side of the knuckles for a set of 15 elements; accordingly, one square box remains empty in the box. The goal of the game is to move the knuckles around the box, to arrange them by numbers, preferably making as few movements as possible.

History

Authorship

From 1891 until his death, Samuel Loyd claimed that it was he who invented the puzzle, and for a long time it was believed that this was really so [6] [7] . However, there is evidence that he was not involved in the creation of "spots", nor in the variation with rearranged chips 14 and 15 [8] [9] [10] [7] . The peak of the popularity of jigsaw puzzles in the USA came in the first half of 1880; however, no mention was made of Sam Loyd in connection with the "tag" until January 1891 [11] [9] . In particular, The New York Times twice published puzzle materials on March 22, 1880 and June 11, 1880, without ever mentioning Loyd, despite the fact that Loyd lived in New York. [12]

The real inventor of the puzzle was Noah Palmer Chapman, postmaster from Canastota [13] [14] , who as early as 1874 showed his friends a puzzle consisting of sixteen numbered squares that had to be stacked in rows of four so that the sum of the numbers in each row was equal to 34 [15] .

Noon Chapman’s son, Frank Chapman, brought the completed puzzles to Syracuse (NY) and handed them to Anna and James Belden [16] . They, in turn, took the puzzle to , where copies of the puzzle were made [13] ; one of these copies didn’t exactly get to Hartford [13] , where students of the began to make rough copies of the puzzle [13] . By 1879, the puzzle was already sold not only in Hartford, but also in Boston . Then the wood artist Matthias J. Rice found out about the "Fifteen". In December 1879, Matthias Rice began a business in Boston to manufacture a new puzzle called The Gem Puzzle [17] [18] [19] .

At the beginning of 1880, a certain Charles Pevy, a dentist from Worcester , attracted public attention by offering a reward for solving the puzzle-collecting task, which added to the popularity of the new fun. In the spring of the same year, the game reached Europe .

On February 21, 1880, Noah Chapman tried to file a patent for his invention under the name “Block Solitaire Puzzle” (“Puzzle - Solitaire with Blocks”) [20] , but the patent application was rejected; there are no records explaining why this happened [21] . Apparently, this was due to the fact that, according to patent inspector Burke, the new application did not differ much from the patent [22] “Tricky blocks”, “Puzzle-Blocks”, issued to Ernest U. Kinsey more than the year before Noah Chapman submitted his application [23] [24] .

Distribution

In the USA

On January 6, 1880, an announcement about a puzzle called Boss Puzzle appeared in the . On January 12, Boston Transcript mentioned several versions of other manufacturers, including Gem Puzzle , Solitaire , Fifteen, and Number Puzzle . On January 19, a puzzle called The New Puzzle was announced in the same newspaper; the next day, the Worcester Gazette posted an ad for The Boss Puzzle . The popularity of the puzzle grew rapidly, and entrepreneurs have already begun its production and sale [25] .

Boston Evening Transcript posted an ad for Matthias Rice between January 26 and 30, annoyed by the appearance of copies of the puzzle. The announcement said [26] :

 
Beware of fakes. Make sure you get this one, carefully crafted, carefully tested puzzle.
Original text (English) :
Rice's Gem Puzzle. The Great Original. Beware of Imitations. Be sure you ask for this, the only accurately made, thoroughly reliable Puzzle in the market, and take no other.

In February 1880, detailed articles on the puzzle began to appear in various newspapers [27] . A number of national magazines, including , Illustrated Newspaper, Harper's Weekly , Scientific American , , have been posting puzzle ads for several weeks [28] . Puzzle news spread to other cities. By early March, many manufacturers released versions of the puzzle under different names [18] .

On February 12, the published a puzzle poem, followed by a series of poetic works in other newspapers [29] . On February 17, an article was published in the newspaper about the impact of the puzzle on society. On February 20, a note appeared in the New York-based Ontario County Journal [30] :

 
Probably N.P. Chapman, the postmaster from Canastota, will be the most damned person in the country over the next few weeks. He invented the Game at 15.
Original text (English) :
Probably NP Chapman, postmaster of Canastota, NY, will, during the coming few weeks, be the most heartily cursed man in the country. He invented the 'Game of 15'.

On March 17, 1880, the published an article that described the “beginning of insanity” in Boston three months ago (in December 1879) [27] .

Based on newspaper ads and articles, the authors of The 15 Puzzle, Slokum and Sonneveld, conclude that in most cities the “madness” lasted one to two months; however, in many cities the puzzle became popular until publications in local newspapers appeared and remained popular even when publications ceased [31] .

Outside the US

In March 1880, the puzzle began to spread outside the United States. Until the end of March, she reached Canada and France. During April, “madness” reached England, Germany, Latvia, Austria, Estonia, Norway, Sweden, Russia, Finland, in May - New Zealand, the Netherlands, Italy, Mexico, Denmark, Australia [32] .

In Russia

April 25, 1880 newspaper in German posted an ad "Neues Spiel - Das Spiel der Funfzehn" [33] ("New Game - Game at 15").

Tasks

The Gem Puzzle

In the puzzle The Gem Puzzle , which was produced and sold by Matthias Rice in 1879, the player poured tiles from the box and randomly laid them back, after which he tried to restore the ordered configuration [19] [9] :

 
Place the blocks in the box in an erratic manner, then move them until they line up in the correct order.
Original text (English) :
Place the blocks in the box irregularly, then move until in regular order.

In this version, the task was unsolvable in exactly half the cases.

Puzzle 14-15

In another version, all tiles, except for 14 and 15, are initially in their places; the task is to swap incorrectly standing tiles 14 and 15. This task is unsolvable; however, in this case, you can arrange the tiles with an empty cell in the upper left corner or arrange the tiles in columns [34] .

  •  

    Fig. 1. In the initial position in the puzzle 14-15, tiles 14 and 15 are interchanged

  •  

    Fig. 2. This location is unattainable from the initial location of puzzle 14-15 (Fig. 1)

  •  

    Fig. 3. But this arrangement is achievable from the initial location of puzzle 14-15 (Fig. 1)

  •  

    Fig. 4. Another achievable arrangement for puzzle 14-15 (Fig. 1)

Modern Modifications

Released many puzzle options. In some cases, instead of arranging numbers, the goal is to restore a certain image. Instead of numbers, letters can be used; the presence of at least two identical letters can make solving the puzzle a non-trivial task.

  •  

    The elephant is sleeping while standing. And you?

  •  

    In English [7]

  •  

    In German

Magic Square

 
Magic square

One of the tasks is to rearrange the tiles so that the sum of the numbers in each row (horizontal, vertical or large diagonal) is equal to the same number ; in this case, the numerical value of the empty cell is considered equal to zero [35] [36] . Moreover, the magic sum is 30. It takes at least 35 moves to get the magic square from the initial location, and there is only one magic square that can be reached in 35 moves [37] .

Mathematical Description

It can be shown that exactly half of all possible 20 922 789 888 000 (= 16 ! ) Initial positions of the spots cannot be reduced to the assembled form: let a square with a numberi {\ displaystyle i}   located to (if you count from left to right and from top to bottom)k {\ displaystyle k}   squares with numbers lessi {\ displaystyle i}   . We assumeni=k {\ displaystyle n_ {i} = k}   that is, if after the knuckle withi {\ displaystyle i}   there are no numbers smaller thani {\ displaystyle i}   thenk=0 {\ displaystyle k = 0}   . Also enter the numbere {\ displaystyle e}   - row number of an empty cell (counting from 1). If the amount

 
Unsolvable combination
N=∑i=one15ni+e{\ displaystyle N = \ sum _ {i = 1} ^ {15} n_ {i} + e}  

is odd , then there is no solution to the puzzle [38] .

If we allow the rotation of the box by 90 degrees, at which the images of the numbers are lying on their sides, then we can translate the insoluble combinations into solvable ones (and vice versa). Thus, if instead of numbers on the knuckles put points and do not fix the position of the box, then there are no insoluble combinations at all.

Optimal Solution

For generalized spots (with more than 15 tiles), the problem of finding the shortest solution for a given configuration is NP-complete [39] [40] .

4 × 4

Any of the 10,461,394,944,000 solvable configurations of the "classic" 4x4 puzzle can be translated into the initial one in no more than 80 moves, if the move means moving one tile [41] [42] [37] [43] , or no more than 43 moves, if the move means the simultaneous movement of a continuous row of no more than three tiles [44] . Only 17 of all solvable configurations cannot be solved in less than 80 moves, that is, they require 80 movements of individual tiles to solve [42] [37] [45] ; only 16 solvable configurations require 43 movements of continuous rows of tiles [44] .

5 × 5

In 1995, it was shown that any 5 × 5 puzzle configuration can be solved in no more than 219 single moves [46] , that is, an upper bound of 219 moves was obtained for the length of the optimal solution for an arbitrary configuration. In 1996, a configuration was found that cannot be solved in less than 112 tile movements [47] . In 2000, the upper bound was improved to 210 moves [48] ; in 2011, for the “ number of God ” of the 5 × 5 puzzle, a lower bound was obtained in 152 moves and an upper bound in 208 moves [43] .

Current Results

The table summarizes the data for a number of generalizations of "tag". When the exact result is not known, the best known lower and upper bounds are given in the form lb - ub .

The sizeTarget configurationThe number of solved
configurations		"Long"
moves [K 1]		" The number of God "Number
"Antipodes" [K 2]
2 × 2empty cell in the corner12not6 [48] [49]1 [48]
2 × 3empty cell in the corner360not21 [48] [49]1 [48]
2 × 4empty cell in the corner20 160not36 [48] [49]1 [48]
2 × 5empty cell in the corner1 814 400not55 [50] [49]2 [50]
2 × 6empty cell in the corner239,500,800not80 [51] [49]2 [51]
2 × 7empty cell in the corner43 589 145 600not108 [52] [49]
2 × 8empty cell in the corner10 461 394 944 000not140 [52] [49]
3 × 3empty cell in the corner181 440not31 [48] [43] [49]2 [48] [53]
Yes24 [43]
3 × 4empty cell in the corner239,500,800not53 [48] [49]18 [48]
3 × 5empty cell in the corner653,837,184,000not84 [49]
3 × 5empty cell in the center653,837,184,000not84 [54]
4 × 4empty cell in the corner10 461 394 944 000not80 [42] [37] [43] [49]17 [42] [37] [45]
Yes43 [44]16 [44]
5 × 5empty cell in the corner7.7556⋅10 24not152 [43] - 208 [43]

The Use of Fifteen in Computer Science

“Fifteen” of various sizes since the 1960s are regularly used in research in the field of AI ; in particular, they search and compare state-space search algorithms with different heuristic functions [55] [56] [57] [58] and other optimizations that affect the number of puzzle configurations (graph vertices) visited during the search. In the research, one way or another, puzzles of the sizes 3 × 3 [59] [60] , 4 × 4 [61] [62] [42] , 5 × 5 [47] [63] [64] , 6 × 6 [65] were used , 2 × 7 [54] , 3 × 5 [54] .

We can list the main reasons for choosing tag as a “test bench” for search algorithms [66] [39] [67] :

  1. the state space of classical spots is accessible for analysis, but still large enough to be of interest and to use and compare various heuristics [68] ;
  2. no algorithm is known that finds the shortest solution for generalized n × n spots in a reasonable time [39] ;
  3. the very task of finding the shortest solution for tricks is simple for understanding and software manipulation [55] [39] ; the puzzle can be described using a small and well-defined set of simple rules [69] [39] ;
  4. puzzle simulation does not require the transfer of semantic subtleties inherent in more complex subject areas [70] ;
  5. tag problems are successful representatives of the class of problems in which it is necessary to find the shortest path between two given vertices of an undirected finite graph [39] ;
  6. the size of the search graph depends on the size of the puzzle n exponentially, although any state can be described with the cost of O ( n 2 ) memory [39] ;
  7. the same heuristic function can be applied to all states, since all states are described in the same way; in real applications, different states may have different descriptions, which requires the introduction of several heuristics [71] ;
  8. the use of games and puzzles in research does not cause financial or ethical problems [70] .

Heuristic Search

As the search algorithm, the algorithm A * , IDA * [72] , breadth-first search can be used.

The 3 × 3 puzzle is easily solved by any search algorithm. Arbitrary configurations of 4x4 spots are solved using modern search algorithms in a few milliseconds [56] . For the optimal solution of the 5 × 5 puzzle, greater resource costs are required even with the use of modern computers and algorithms [56] [63] ; the search process can last several weeks and generate trillions of nodes [64] [65] . The optimal solution for arbitrary 6 × 6 puzzle configurations is still beyond the scope of possibilities [65] , and therefore, studies only attempt to predict the relative performance of the IDA * algorithm with different heuristic functions [65] .

One of the simplest heuristics for tag can be expressed as follows [73] [74] [75] :

The number of moves required to solve is not less than the number of tiles that are not in their places.

The validity of the statement, that is, the admissibility of the heuristic function “the number of tiles that are not in their places”, follows from the fact that only one tile can be put in place in one move. This heuristic does not use all available information: for example, it does not take into account the distances over which individual tiles must be moved.

More “smart” heuristics correlates to each tile arrangement the sum of the distances from the current position of each tile to its target position [76] . In the literature, this heuristic is found under the name "Manhattan distance" (Manhattan distance) [75] [77] . The admissibility of the function follows from the fact that only one chip moves in a single move, and the distance between this chip and its final position changes by 1. However, this heuristic also does not use all available information, due to the fact that in one position two tiles cannot be at the same time. There are more informed versions of the “Manhattan distance”, such as Linear Conflict [57] .

To quickly search for the optimal 4 × 4 puzzle solution, as well as to be able to find the optimal 5 × 5 puzzle solution in a reasonable amount of time, heuristics based on pattern databases [62] [63] [58] have been developed. Such heuristics are essentially pre-computed and stored in random access memory tables in which optimal solutions for subtasks are encoded; Each of the subtasks is reduced to moving to a target position a certain group of tiles [62] . These heuristics can also be applied to Rubik's cube and other puzzles [63] .

See also

  • Rubik's Cube
  • Minus cube

Comments

  1. ↑ The column indicates whether the simultaneous movement of several tiles forming a continuous vertical or horizontal row is considered in one move.
  2. ↑ “Antipodes” - puzzle configurations that require the greatest number of moves to solve

Notes

  1. ↑ Mathematical leisure, 1972 , p. 401.
  2. ↑ 1 2 Interesting tasks and experiments, 1972 , p. 365.
  3. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 43, 114, 163, 166, 168, 181-182.
  4. ↑ 1 2 The name "Fifteen" (neopr.) . TwistyPuzzles.RU.
  5. ↑ Vladimir Belov. Puzzles from near distance. Part 2 (neopr.) . Computerra (January 18, 2000). Archived on November 28, 2015.
  6. ↑ Cyclopedia of Puzzles , p. 235
  7. ↑ 1 2 3 Jaap Scherphuis. 14-15 puzzle / Boss puzzle (neopr.) . Jaap's Puzzle Page .
  8. ↑ The 15 Puzzle, 2006 .
  9. ↑ 1 2 3 Review of The 15 Puzzle by Aaron Archer , p. one.
  10. ↑ Puzzles for Pleasure, 1994 , p. 10-12.
  11. ↑ The 15 Puzzle, 2006 , p. 76.
  12. ↑ Puzzles for Pleasure, 1994 , p. eleven.
  13. ↑ 1 2 3 4 The 15 Puzzle, 2006 , p. 109.
  14. ↑ Review of The 15 Puzzle by Aaron Archer , p. 13.
  15. ↑ The 15 Puzzle, 2006 , p. 98-99.
  16. ↑ The 15 Puzzle, 2006 , p. 103-104, 109.
  17. ↑ The 15 Puzzle, 2006 , p. 11, 109.
  18. ↑ 1 2 Review of The 15 Puzzle by Aaron Archer , p. 2.
  19. ↑ 1 2 Jerry Slocum: Sam Loyd's Most Successful Hoax (PDF; 672 kB) . Vortrag auf: Seventh Gathering for Gardner, March 2006, The Convention of the Association of Game and Puzzle Collectors. Publiziert in: E. Pegg, AH Schoen & T. Rodgers: Homage to a Pied Puzzler. AK Peters, Wellesley / Massachusetts, 2009, S. 3-21. (hier: S. 4)
  20. ↑ The 15 Puzzle, 2006 , p. 100-101.
  21. ↑ The 15 Puzzle, 2006 , p. 101.
  22. ↑ EU Kinsey. Puzzle-Blocks. No. 207124. Patented Aug. 20, 1878 (neopr.) .
  23. ↑ The 15 Puzzle, 2006 , p. 102.
  24. ↑ Review of The 15 Puzzle by Aaron Archer , p. 3.
  25. ↑ The 15 Puzzle, 2006 , p. 14-15.
  26. ↑ The 15 Puzzle, 2006 , p. 15-16.
  27. ↑ 1 2 The 15 Puzzle, 2006 , p. 12.
  28. ↑ The 15 Puzzle, 2006 , p. 20.
  29. ↑ The 15 Puzzle, 2006 , p. 21.
  30. ↑ The 15 Puzzle, 2006 , p. 24, 98.
  31. ↑ The 15 Puzzle, 2006 , p. 59.
  32. ↑ The 15 Puzzle, 2006 , p. 60.
  33. ↑ The 15 Puzzle, 2006 , p. 63.
  34. ↑ Interesting tasks and experiments, 1972 , p. 370
  35. ↑ Interesting tasks and experiments, 1972 , p. 371.
  36. ↑ Sam Loyd; Martin Gardner: Mathematical puzzles of Sam Loyd . Dover Pubs., New York 1959, pp. 19 und 20. Google books
  37. ↑ 1 2 3 4 5 Herbert Kociemba. Fifteen Puzzle Optimal Solver (Neopr.) . Archived on October 2, 2015.
  38. ↑ Slocum J., Weisstein EW 15 Puzzle on the Wolfram MathWorld website.
  39. ↑ 1 2 3 4 5 6 7 Ratner D., Warmuth MK Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable // National Conference on Artificial Intelligence, 1986.
  40. ↑ Ratner D., Warmuth M. The (n 2 −1) -puzzle and related relocation problems // Journal of Symbolic Computation. - 1990. - T. 10 , No. 2 . - S. 111–137 . - DOI : 10.1016 / S0747-7171 (08) 80001-6 .
  41. ↑ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications , Annals of Operations Research 90 (1999), pp. 45-63.
  42. ↑ 1 2 3 4 5 Richard E. Korf, Peter Schultze. Large-Scale Parallel Breadth-First Search . - 2005.
  43. ↑ 1 2 3 4 5 6 7 Sequence A087725 in OEIS : the greatest number of moves that may be required to summarize the n × n puzzle “tag”
  44. ↑ 1 2 3 4 Bruce Norskog. The Fifteen Puzzle can be solved in 43 "moves" (neopr.) . Domain of the Cube Forum (December 8, 2010).
  45. ↑ 1 2 Sequence A089484 in OEIS : number of tag configurations whose optimal solution contains n moves
  46. ↑ Ralph Udo Gasser. Harnessing Computational Resources for Efficient Exhaustive Search . - 1995.
  47. ↑ 1 2 Richard E. Korf, Larry A. Taylor. Finding Optimal Solutions to the Twenty-Four Puzzle . - 1996.
  48. ↑ 1 2 3 4 5 6 7 8 9 10 11 Filip RW Karlemo and Patric RJ Östergård On Sliding Block Puzzles , Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107
  49. ↑ 1 2 3 4 5 6 7 8 9 10 11 A151944 sequence in OEIS : the largest number of moves that may be required to summarize the m × n puzzle “tag”
  50. ↑ 1 2 Sequence A090036 in OEIS
  51. ↑ 1 2 Sequence A090167 in OEIS
  52. ↑ 1 2 Sequence A151943 in OEIS
  53. ↑ Sequence A089473 in OEIS
  54. ↑ 1 2 3 Richard E. Korf. Breadth-first frontier search with delayed duplicate detection . - 2004.
  55. ↑ 1 2 Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 114.
  56. ↑ 1 2 3 Artificial Intelligence: A Modern Approach, 2006 , p. 118.
  57. ↑ 1 2 Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, 1985 .
  58. ↑ 1 2 F. Yang, J. Culberson, R. Holte, U. Zahavi and A. Felner A General Theory of Additive State Space Abstractions , Volume 32 (2008), pages 631-662
  59. ↑ Alexander Reinefeld. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA * . - 1993.
  60. ↑ Daniel R. Kunkle. Solving the 8 Puzzle in a Minimum Number of Moves: An Application of the A * Algorithm . - 2001.
  61. ↑ Richard E. Korf. Depth-first Iterative-Deepening: An Optimal Admissible Tree Search . - 1985.
  62. ↑ 1 2 3 Joseph C. Culberson, Jonathan Schaeffer. Pattern Databases . - 1998.
  63. ↑ 1 2 3 4 Richard E. Korf. Recent Progress in the Design and Analysis of Admissible Heuristic Functions . - 2000.
  64. ↑ 1 2 Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics . - 2002.
  65. ↑ 1 2 3 4 Ariel Felner, Richard E. Korf, Sarit Hanan. Additive Pattern Database Heuristics . - 2004.
  66. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 43, 114, 163.
  67. ↑ Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, 1985 , p. 3.
  68. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 114, 163.
  69. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 43, 163.
  70. ↑ 1 2 Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 43.
  71. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 163.
  72. ↑ Borowski BS Optimal 8/15-Puzzle Solver (neopr.) . // Brian's Project Gallery. Date of treatment July 29, 2013. Archived August 17, 2013.
  73. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 156.
  74. ↑ Entertaining Programming: Self-Tutorial, 2005 , p. 171.
  75. ↑ 1 2 Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, 1985 , p. 4-5.
  76. ↑ Artificial Intelligence: Strategies and Methods for Solving Complex Problems, 2003 , p. 157.
  77. ↑ Entertaining Programming: Self-Tutorial, 2005 , p. 173.

Literature

Books
  • Gardner M. Mathematical Leisure / Per. from English Yu.A. Danilova . Ed. J. A. Smorodinsky . - M .: Mir , 1972.
  • Perelman Ya. I. Entertaining tasks and experiments. - M .: Children's literature , 1972.
  • Jerry Slocum and Dic Sonneveld. The 15 Puzzle. - 2006. - ISBN 1-890980-15-3 .
  • In the footsteps of Pythagoras: Entertaining mathematics = Śladami Pitagorasa / Translation from Polish by G.F. Boyarskaya, B.V. Boyarsky and A.A. Yakushev. - M .: Detgiz , 1961 .-- S. 231-233.
  • Clarke BR Puzzles for Pleasure . - Cambridge University Press, 1994. - ISBN 0-521-46634-2 .
  • Luger, George F. Artificial Intelligence: Strategies and Methods for Solving Complex Problems = Artificial Intelligence: Structures and Strategies for Complex Problem Solving. - 4th edition. - Williams Publishing House, 2003. - 864 p. - ISBN 5-8459-0437-4 . - ISBN 978-5-845-90437-9 .
  • Stuart Russell, Peter Norwig . Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach. - 2nd ed. - M .: Williams Publishing House, 2006. - 1408 p. - ISBN 5-8459-0887-6 .
  • Mozgovoy M.V.Entertaining programming: a self-instruction manual . - SPb. : Peter , 2005 .-- 208 p. - ISBN 5-94723-853-5 .
Articles
  • Wm. Woolsey Johnson, and William E. Story. 1879. Notes on the „15“ Puzzle ” . American Journal of Mathematics 2 (4). The Johns Hopkins University Press: 397–404. doi: 10.2307 / 2369492.
  • Aaron Archer. The 15 Puzzle: How it Drove the World Crazy by Jerry Slocum and Dic Sonneveld .
  • Othar Hansson, Andrew E. Mayer, Mordechai M. Yung. Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models . - 1985.

Links

  • Optimal 8/15-Puzzle Solver // brian-borowski.com (Java source)
  • “15puzzle Optimal solver” for Windows - Ken'ichiro Takahashi (takaken)
  • Fifteen Puzzle Optimal Solver - Herbert Kociemba`s Homepage
  • Fifteen.com - Play Fifteen online
Source - https://ru.wikipedia.org/w/index.php?title=Game_15_old&oldid=99130395


More articles:

  • Morskoye (Black Sea region)
  • Ilinčić, Zlatko
  • Nikolaev, Alexander Panfomirovich
  • Danish-Norwegian operation
  • Khabarovsk Planetarium
  • Panteleimon (Rozhnovsky)
  • Myrmeconema neotropicum
  • Pechora County (Estonia)
  • Botvinovsky Village Council
  • Krasnobudsky Village Council

All articles

Clever Geek | 2019