home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17183 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  3.1 KB
  1. Xref: sparky sci.math:17183 rec.games.abstract:652
  2. Path: sparky!uunet!mcsun!sun4nl!tuegate.tue.nl!rw6.urc.tue.nl!rcbaaw
  3. From: rcbaaw@rw6.urc.tue.nl (Angelo Wentzler)
  4. Newsgroups: sci.math,rec.games.abstract
  5. Subject: Re: Game of pentominos
  6. Message-ID: <rcbaaw.724692264@rw6.urc.tue.nl>
  7. Date: 18 Dec 92 15:24:24 GMT
  8. References: <1992Dec15.154734.23894@odin.diku.dk> <pete.03it@bignode.equinox.gen.nz>
  9. Sender: root@tuegate.tue.nl
  10. Reply-To: rcbaaw@urc.tue.nl
  11. Followup-To: sci.math
  12. Lines: 62
  13.  
  14. pete@bignode.equinox.gen.nz (Pete Moore) writes:
  15.  
  16. >Torben AEgidius Mogensen (torbenm@diku.dk) wrote:
  17. >>martel@marvin.mr.sintef.no (Paulo Martel) writes:
  18.  
  19. >>>After several tries I gave up a combinatorial analysis of the game of
  20. >>>pentominos. Would someone point me to a reference, or briefly explain
  21. >>>how one could compute the total number of solutions for a grid of a
  22. >>>given size (6x10, 5x12, 4x15, 3x20). 
  23.  
  24. >>I saw a paper once that reported the number of solutions to each of
  25. >>these rectangle sizes. It used a heavily optimized machine code
  26. >>program to exhaustively search for all solutions. I remember that for
  27. >>the 3x20 case there are only two solutions barring reflections and
  28. >>rotations. These are quite easy to find by hand. The number of
  29. >>solutions for the 6x10 case was quite large, but I don't recall the
  30. >>number. I also don't recall the title or author of the paper.
  31.  
  32. >I can't give an authoritative reference, but according to
  33. >some notes I made back in my young & innocent days when I used to note
  34. >information without references, there are:
  35. >     2  3x20 solutions
  36. >  2339  6x10 solutions
  37. >  1010  5x12 solutions
  38. >   368  4x15 solutions
  39.  
  40. >If your pentominoes are 3-dimensional (i.e. each could be constructed by
  41. >joining 5 cubes together) rather than 2-dimensional, you can also form a
  42. >3x4x5 rectangular prism from the 12 pentominoes. 
  43.  
  44. Gee, this must be my lucky month! I like pentominoes, wrote a program
  45. once (who didn't) and I rank them right up there along with life,
  46. rubik's cube and tiled squares (See: tiling problem in this group :-)
  47.  
  48.  
  49. C.J.Bouwkamp, a professor here at the TUE has computed all solutions
  50. to this prism as well as to "the steps" which is a three dimensional
  51. staircase. He's just as mad about pentominoes as I am.
  52.  
  53. The catalogues are:
  54.  
  55. "Catalogue of solutions to the rectangular 3x4x5 pentomino problem"
  56. C.J.Bouwkamp, Eindhoven University of Technology.
  57.  
  58. "Packing the steps with solid pentominoes"
  59. C.J.Bouwkamp, Eindhoven University of Technology.
  60.  
  61. The books are available here, but not in "computerised" format.
  62.  
  63.  
  64. By the way, has anybody ever tried to write a program to compute all
  65. (N+1)-ominoes from the set of N-ominoes? It's not difficult:
  66. Just take one N-omino at a time and fit an extra square onto it. This
  67. produces one extra (N+1)-omino. Fit a square on all possible positions,
  68. (just "roll" it along the edge) then proceed with the next N-omino.
  69. This leaves you with a *bag* of (N+1)-ominoes, of which you now have to
  70. make a *set* (remove multiple copies).
  71. It would be smart to check for multiples right at the start though...
  72.  
  73. It would take a lot of computation, but not an awful lot of time.
  74.  
  75. Angelo Wentzler
  76.