Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #14057

pentominoes in 5 by 12 box

Show all headers | View raw

I have been thinking about a totally different way to attack the
pentomino problem: how to fit pentominoes in a 5 by 12 box.

It is based on keeping information about the boundary, not the bulk.
The boundary is represented by a sequence of L(eft) R(ight) S(traight)
edges.

E.g. the piece

****
*

Is represented  (anti-clockwise) LSLLRSSLLSSS

The field is represented (5x12)
LS(*4)LS(*11)LS(*4)LS(*11)

If we encode : S -> 11 L -> 01 R -> 10
we are left with a 00 -> X (don't care).

Now we can store a boundary in a double (128 bit) number.
The rules:
   pairs of 0 bits are ignored.
   rotating by a multiple of 2 bits leads to an equivalent boundary.
   the number of L's minus the number of R's must be 4
   the number of edges is even.

Now we can subtract the L-piece from the boundary.
LSLLRSSLLSSS  -> LLRSSLLSSSLS     rotate a few edges

LSSSSLSSSSSSSSSSLSSSSLSSSSSSSSSS              match
             |||||
             SSSLS
      LLRSSLL

The remainder of the boundary is replacing the fitting part:
by the rules
       flip   RRLSSRR and
     reverse LRSSLRL
             |     /
LSSSSLSSSSSSSSSSLSSSSLSSSSSSSSSS   insert
             ||||||
             SSSLSS

LSSSSLSSSSSSSLRSSLRLSSSLSSSSSSSSSS   result

The final algorithm should become
   REPEAT
        find toughest corner
        repeat
            recurse with a piece/position that fits there

The hard part is
        identifying impossible boundaries, when they intersect themselves.
        define toughness

I'm interested if anybody gets this programmed.

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Back to comp.lang.forth | Previous | Next | Find similar

Thread

pentominoes in 5 by 12 box Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-16 15:24 +0000

csiph-web