home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17263 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  1.7 KB
  1. Path: sparky!uunet!spool.mu.edu!agate!doc.ic.ac.uk!news!dbh
  2. From: dbh@doc.ic.ac.uk (Denis Howe)
  3. Newsgroups: sci.math
  4. Subject: Re: Game of pentominos
  5. Followup-To: sci.math
  6. Date: 21 Dec 92 15:23:55
  7. Organization: Computing Department, Imperial College, London, UK
  8. Lines: 24
  9. Distribution: world
  10. Message-ID: <DBH.92Dec21152355@wombat.doc.ic.ac.uk>
  11. References: <1992Dec15.154734.23894@odin.diku.dk>
  12.     <pete.03it@bignode.equinox.gen.nz>
  13.     <rcbaaw.724692264@rw6.urc.tue.nl>
  14. NNTP-Posting-Host: wombat.doc.ic.ac.uk
  15. In-reply-to: rcbaaw@rw6.urc.tue.nl's message of 18 Dec 92 15:24:24
  16.  
  17. In article <rcbaaw.724692264@rw6.urc.tue.nl> rcbaaw@rw6.urc.tue.nl
  18. (Angelo Wentzler) wrote:
  19.  
  20. >has anybody ever tried to write a program to compute all
  21. >(N+1)-ominoes from the set of N-ominoes?  It's not difficult: Just
  22. >take one N-omino at a time and fit an extra square onto it.  This
  23. >produces one extra (N+1)-omino.  Fit a square on all possible
  24. >positions, (just "roll" it along the edge) then proceed with the next
  25. >N-omino.
  26.  
  27. This is precisely how a very old Basic program of mine works.  You
  28. start off with one square (the set of 1-ominoes), add another to the
  29. right then roll it round the outside to generate all 2-ominoes etc..
  30. You then apply the eight reflections and rotations, shift each shape
  31. generated so that its minimum x and y coords are both 0 and compare it
  32. with all previously found n-ominoes.  It's this last step that is the
  33. boring bit.  Anyone come up with any good hashing functions for
  34. ominoes?  Centre of gravity?  Moment of inertia?
  35.  
  36. Mail me if you want the program.  It's in Acorn Basic and runs on the
  37. Archimedes.
  38. --
  39. Denis Howe <dbh@doc.ic.ac.uk>
  40. So Biggs, you're the idiot who bought all these IBM PCs.  You're fired!
  41.