home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17032 < prev    next >
Encoding:
Internet Message Format  |  1992-12-16  |  1.8 KB
  1. Xref: sparky sci.math:17032 rec.games.abstract:633
  2. Newsgroups: sci.math,rec.games.abstract
  3. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!agate!linus!progress!neil
  4. From: neil@progress.COM (Neil Galarneau)
  5. Subject: Re: Game of pentominos
  6. Message-ID: <1992Dec16.182611.10896@progress.com>
  7. Sender: usenet@progress.com (Mr. Usenet)
  8. Nntp-Posting-Host: pinta
  9. Organization: Progress Software Corp.
  10. References: <martel.724342292@marvin> <1992Dec15.154734.23894@odin.diku.dk>
  11. Date: Wed, 16 Dec 1992 18:26:11 GMT
  12. Lines: 38
  13.  
  14. torbenm@diku.dk (Torben AEgidius Mogensen) writes:
  15.  
  16. >martel@marvin.mr.sintef.no (Paulo Martel) writes:
  17.  
  18. >>After several tries I gave up a combinatorial analysis of the game of
  19. >>pentominos. Would someone point me to a reference, or briefly explain
  20. >>how one could compute the total number of solutions for a grid of a
  21. >>given size (6x10, 5x12, 4x15, 3x20). 
  22.  
  23. >I saw a paper once that reported the number of solutions to each of
  24. >these rectangle sizes. It used a heavily optimized machine code
  25. >program to exhaustively search for all solutions. I remember that for
  26. >the 3x20 case there are only two solutions barring reflections and
  27. >rotations. These are quite easy to find by hand. The number of
  28. >solutions for the 6x10 case was quite large, but I don't recall the
  29. >number. I also don't recall the title or author of the paper.
  30.  
  31. >    Torben Mogensen (torbenm@diku.dk)
  32.  
  33. Ah... Good old pentominoes.
  34.  
  35. Several years ago, motivated by a passage in one of Clarke's novels, several
  36. of us programmed pentominoes.
  37.  
  38. It is not very hard to solve it, it is a lot harder to solve it efficiently.
  39.  
  40. The programming was a lot of fun.
  41.  
  42. There are about 2100 solutions to the 6x10 case.
  43.  
  44. A slow program will take 30 seconds per solution, a fast one can take less
  45. than 5 seconds per solution.
  46.  
  47. We didn't try other board sizes.
  48.  
  49.  
  50. Neil
  51. neil@progress.com
  52.