[geeks] Pentominos continued

[Mouse]

> Deleted the posts since the math went over my head so sorry for
> screwing up the threading after reconsidering.

Well, as far as I personally am concerned, no big deal; my list
threading happens in wetware and doesn't depend on References:. :-)

> Mouse, I am guessing you coded this in C [...]

Right.  All the programs in question are in C.  (Or, at least, the
language I usually think of as C, which is actually C plus gcc
extensions plus an extension of my own, though that last I see I didn't
use in the programs you're likely to care about.)

> Have you tried / is it possible to apply some parallelization stuff
> like OpenMP to make this faster?  Do you have a multicore box to try
> it on?

I have two dual-core machines readily available; I have another
two-core and a four-core that would require digging them out.  But a
speedup of small factors, like available core count, isn't going to
make much difference.  Ten _orders of magnitude_ improvement (not to be
confused with factor of ten) still wouldn't put the full problem within
reach of brute force.

> If you would share your algorithm it might be interesting to see what
> other people could come up with using other languages, tools etc.

Well, it's all available in git repos.  (I am aware there are people
who don't like git.  I can explain why it's what I use if anyone cares,
but that's a bit off-topic for this thread.)  The thing to point git
clone at is git://git.rodents-montreal.org/Mouse/pack.  The
general-purpose solver is `fast', in the top-level directory;
format.reply describes the puzzle format, and there are many exmaples
(eg, the files in pentomino/ that have .out siblings next to them, like
4x15 or 63).  sgraphic is a program which draws ascii-graphics images
of things.  For example, one of the solutions to the 5x12 pentomino
rectangle is (as it appears in 5x12.out)

(WLLLLYNFFPPP) (WWZZLYNNFFPP) (TWWZYYVNFXUU) (TTTZZYVNXXXU) (TIIIIIVVVXUU)

Feed this line to sgraphic and the result is

 _______________________
| |_____  | | |_  |_    |
|_  |_  |_| |_  |  _|___|
| |___| |_  | | |_| |_  |
|  ___|___|_| |_|_   _| |
|_|_________|_____|_|___|

It can do line-drawing characters as well, for VT-100s or TVI-955s or a
few others - see the charsets[] array in the source - by running, eg,
"sgraphic -chars vt100".  There are other options - there isn't any
real documentation at the moment, but there will be soon; I'm going to
write up a comment header for sgraphic.c and will commit/push it as
soon as it's done.

> That is, if you're still interested in brute-forcing this.

Well, I'm interested in solving the problem.  Brute force is one
possible tool, one which has proven useful for some related problems,
but I'm certainly not going to try to brute-force enumeration of
something on the order of 10^34.  Even less so with doing a nontrivial
amount of work for each enumerated thing.  (With the magnified
15-ominos, I'm running my pentomino-puzzle solver for each of the 3.4+
million 15-ominos.)

> If it was the math you're after then get back to us after somebody
> gives you the equations ;-)

:-)

I was mostly wondering if there's some work already done that had
determined what shape had the most solutions, somehow.  Secondarily,
wondering if anyone had any suggestions for how to approach it.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		mouse at rodents-montreal.org
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B