Pentomino question: 8x8
Nicholas Gray
to the 8x8 square filled with all the pentominoes and the square
tetromino? I got this with a program I wrote (it took a very long
time), but it does seem a bit big.
Nick
Jan Kok
For the tetromino right in the middle the result is well known to be
65 basicly different solutions. I have a Penguin edition of Martin
Gardner's 'More mathematical diversions' (1966?) at home, where it is
written that Dana Scott solved this problem by computer in 1962.
Solutions also exist for the tetromino in other positions on the
board, but not that large figures. Eliminate those obtainable by
rotation or reflecting.
--
--Jan Kok
Mail: CWI (dpt. NW)/P.O.Box 94079/NL-1090 GB Amsterdam//E-mail: Jan...@cwi.nl
--------------------------------------------------------- From students' exams:
The process of turning steam back into water again is called conversation
Jan Kok
: In article <2jd1gm$6...@salmon.maths.tcd.ie> asdf...@maths.tcd.ie (Nicholas Gray) writes:
: > Can somebody confirm the rather large figure of 32292 solutions
: >to the 8x8 square filled with all the pentominoes and the square
:
: For the tetromino right in the middle the result is well known to be
: 65 basicly different solutions. I have a Penguin edition of Martin
: Gardner's 'More mathematical diversions' (1966?) at home, where it is
: written that Dana Scott solved this problem by computer in 1962.
: Solutions also exist for the tetromino in other positions on the
: board, but not that large figures. Eliminate those obtainable by
: rotation or reflecting.
Corrections:
- The Penguin edition was titled : Mathematical puzzles and diversions (1965),
- it says that Dana Scott computed the 65 solutions on the MANIAC in 1958.
Actually, Gardner also wrote that the number of solutions with the
tetromino placed anywhere is much larger. I have to look up the results
elsewhere.
Nicholas Gray
particular problem involved a *square* rather than the 3x20, 4x15, 5x12 or 6x10
rectangles it was designed for), and testing it on the particular case with the
2x2 square in the middle, I have to revise my previous value. I haven't run the
new program yet but it should get only half the previous number when I do.
SOMEBODY must be able to confirm this figure, because I'm sure the problem has
been tackled before. It's probably 16146, but again this sounds to high. I'll
post the results of the program in a couple of days.
Nick
Dik T. Winter
the square tetronimo. For those 10 ways I found the following table
(in front are the coordinates of the square tetronimo):
1,1: 5027
1,2: 3207
1,3: 1839
1,4: 1288
2,2: 987
2,3: 1662
2,4: 721
3,3: 582
3,4: 768
4,4: 65
These all count rotations, mirror reflections etc. as one. The total
is 16146 which looks surprisingly like one half of what you had. I
assume you counted rotations as one but mirror reflections as different.
(It took 15 hours computing. Of these 5 hours where spend on the first
and 7 seconds on the last. But that is, I think, more than was needed
because of some suboptimal strategy I am going to correct.)
Why do you think it is a bit big? Because it is so difficult to find a
solution by hand? Remember that there are similar puzzles that allow
billions of solutions and that are nearly impossible to do by hand.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: d...@cwi.nl
Nicholas Gray
>Why do you think it is a bit big? Because it is so difficult to find a
>solution by hand? Remember that there are similar puzzles that allow
>billions of solutions and that are nearly impossible to do by hand.
Well actually I thought it was a bit big because there were only 65
solutions for the 2x2 in the middle! If you estimate the number of
solutions as being of the order of 100 for each position it can be in
the you can "estimate" the total number of solutions as being of the
order of 1000, which is way out from the true value (explicable by the
increase in ease of finding a solution when the 2x2 is nearer the edges
and not being awkward). Also I'd never tried my program on anything this
big before, so lack of faith had something to do with it.
Speaking of similar puzzles which are nearly impossible to do by hand,
but on the other extreme, does anybody know if there is a CHECKERED
set with only ONE solution ie. all the pentominoes and the tetromino are
coloured checkerboard fashion, the object being to form a full 8x8
board with the check pattern correct. As far as I know the best is
Dudeney's set, which has 4 solutions. Is this the best?
Nick