From: Yann DAVID <100552.1400@CompuServe.COM>
Date: 5 Jan 1997 19:20:19 GMT
Newsgroups: comp.theory,rec.puzzles,sci.logic,sci.math
Subject: Polymino inclusion problem
Hello.
Problem: given a finite family of polyminoes (of any sizes), is the set
of the polyminoes that do NOT contain any member of the family finite
or infinite?
NB:
- polyminoes are those geomatrical figures obtained by sticking some
squares together along their sides (so as to come up with a connex
result);
- a polymino A is said to contain a polymino B if one can cover an
instance of B with an instance of A; in other words, one can get a 'B'
by chopping off some squares from a 'A'.
My question is: what is the status of the above problem? That is, is there
any general solution to it? If not, is the problem [known to be]
undecidable? If yes, what is its complexity?
The problem was suggested by "Winning Ways" (Berlekamp, Conway & Guy),
volume 2, page 684 -they exhibit a finite family of polyminoes that
are distinguished by the fact that they do not contain any member of
another finite family of poliminoes.
All I have found out so far is the pretty obvious fact that the set of
the polyminoes which do not contain any instance of the "target" family
is finite if and only if there is a generation of polyminoes (all the
polyminoes of a given size) such that every member of the generation
contains at least one member of the family. All subsequent generations
share, of course, the same property. The problem can then be restated
in terms of finding the order of a "critic" generation, given a target
family (one would have "only" to test every member of the critic generation
- does it contain any member of the target family? that question is NOT
difficult - so as to decide whether the non-containing set is finite or
not.
Notice that the reverse problem is quite entertaining too: given a finite
family of poliminoes, is there any other finite family such that the first
one is the family of all those that do not contain any member of the
second one?
Have fun! All suggestions, clues, hints, remarks, references & solutions
are welcome.
Best regards,
Yann David
100552.1400@compuserve.com
FRANCE
NB: Since I am not a regular reader of this newsgroup,
please e-mail your answers; I'll post a summary of the interesting
ones (if any! :).
"Vous mariez pas, les filles!" - Boris Vian
From: Yann DAVID <100552.1400@CompuServe.COM>
Date: 31 Jan 1997 20:09:45 GMT
Newsgroups: comp.theory,rec.puzzles,sci.logic,sci.math
Subject: POLYOMINOES EXCLUSION SET - ANSWERS
Hello.
Here are the answers I received in response to my post about
polyominoes excluding a finite set of polyominoes (are there
finitely or infinitely many of them?). We did not come up
with any definite solution, but there were some very interesting
hints towards a plausible solution.
Here goes:
Original post:
Problem: given a finite family of polyminoes (of any sizes), is the set
of the polyminoes that do NOT contain any member of the family finite
or infinite?
NB:
- polyminoes are those geomatrical figures obtained by sticking some
squares together along their sides (so as to come up with a connex
result);
- a polymino A is said to contain a polymino B if one can cover an
instance of B with an instance of A; in other words, one can get a 'B'
by chopping off some squares from a 'A'.
My question is: what is the status of the above problem? That is, is there
any general solution to it? If not, is the problem [known to be]
undecidable? If yes, what is its complexity?
The problem was suggested by "Winning Ways" (Berlekamp, Conway & Guy),
volume 2, page 684 -they exhibit a finite family of polyminoes that
are distinguished by the fact that they do not contain any member of
another finite family of poliminoes.
All I have found out so far is the pretty obvious fact that the set of
the polyminoes which do not contain any instance of the "target" family
is finite if and only if there is a generation of polyminoes (all the
polyminoes of a given size) such that every member of the generation
contains at least one member of the family. All subsequent generations
share, of course, the same property. The problem can then be restated
in terms of finding the order of a "critic" generation, given a target
family (one would have "only" to test every member of the critic generation
- does it contain any member of the target family? that question is NOT
difficult - so as to decide whether the non-containing set is finite or
not.
Notice that the reverse problem is quite entertaining too: given a finite
family of poliminoes, is there any other finite family such that the first
one is the family of all those that do not contain any member of the
second one?
Wei-Hwa Huang wrote:
(1st message)
>I don't know about the the problem, but if it is true, it would sound
>very similar to Sylvester's Theorem and make a darned good variation
>of Sylver Coinage.
(2nd message)
>Sylvester's Theorem (in this case; he had a lot of other theorems)
>says that given any two relatively prime positive integers, only
>a finite number of positive integers cannot be expressed as a sum
>of non-negative multiples of these two integers.
>
>For instance, all integers greater than 100 can be expressed as
>some non-negative multiple of 9 plus some non-negative multiple of
>10.
>
>In Winning Ways the game Sylver Coinage is introduced; basically,
>two people alternate saying positive integers, where you cannot say any
>integers that can be expressed as a sum of non-negative multiples of
>all the integers previously said.
>
>The person who says 1 loses.
>
>You can see the similarity between your game and Sylver Coinage, I hope.
Dan Hoey wrote:
>The word "polyomino" is the more widely-used term, or "n-omino" for
>what you call "generation n".
>
>I haven't heard of your problem before, even of it being posed. I'll
>have a look at _Winning Ways_. Do you know of any other references?
I answered:
You won't find a clear statement of that problem in _Winning Ways_,
it is just hinted at there. I don't know of any other reference, but
such a simple problem must have been posed in some book or article
already.
He wrote:
>Now that I've looked it up, I see. One thing I see is that the
>problem is very close to the "unavoidable subgraph" problem that was
>used in solving the four-color theorem. We ask whether given a finite
>set of graphs H and an infinite set of graphs G, whether all but
>finitely many elements of G have an element of H as subgraph. In that
>general setting, I'm almost certain it's undecidable. I don't know if
>there's any way to make it easier by using the fact that G is a
>representation of the polyominoes.
>
>While looking it up, I ran across the Sprouts discussion, and the
>FTOZOM. It looks surprisingly like another instance of the same
>problem.
David Moews made, in my opinion, the most interesting contribution. He wrote:
>Given any polyomino P, let G(P) be the (connected) graph obtained from P
>by placing a vertex at each square of P and joining two vertices iff their
>squares are neighboring. Call P a snake if G(P) is a path. Now we can
>restrict our attention to snakes, in the sense that
>
> given a family S, the set of polyominoes not containing any member of S
> is finite iff the set of snakes not containing any snake member of S is
> finite.
>
>The left-to-right implication is obvious, since no snake can contain a
>non-snake. For the right-to-left implication, if there are infinitely
>many polyominoes not containing any member of S, then there must be
>polyominoes of arbitrarily large size not containing any member of S,
>and we can trim these polyominoes down to arbitrarily long snakes which
>cannot contain any snake member of S.
>
>We can code snakes by strings: e.g., given a snake
>
> ***
> *** **
> *
>
>we can code it as *AB*CD*CD*AB*CD*CD*BA*CD*, writing a * for each square, AB
>for a move up, BA for a move down, CD for a move right, and DC for a move
>left. With this code each snake has exactly 2 representations which are
>reversals of each other (depending on which end you start from,) and snake
>X contains snake Y just when Y's string is a substring of X's string or the
>reversal of X's string. Unfortunately this does not reduce the problem to
>the corresponding problem about strings (which would be decidable) because
>there are many strings which look very much like snakes but are not, owing to
>self-intersection, e.g., *AB*AB*CD*CD*BA*BA*DC*DC*.
>
>
>|...
>|Notice that the reverse problem is quite entertaining too: given a finite
>|family of poliminoes, is there any other finite family such that the first
>|one is the family of all those that do not contain any member of the
>|second one?
>
>Obviously, the first family has to be closed under downwards inclusion.
>Given that it is, and that the maximal order of polyomino present in the
>first family is N, we can let the second set contain all polyominoes of
>order <=N+1 not present in the first.
>--
As I asked why the string problem he stated was decidable, he answered:
>If we have a set S of strings over some alphabet, e.g., {ABC, CCC, CB}
>over the alphabet {A, B, C}, it's easy to write down a regular expression
>that recognizes all strings containing some member of S (in this case,
>
> ((A|B|C)*ABC(A|B|C)*)|((A|B|C)*CCC(A|B|C)*)|((A|B|C)*CB(A|B|C)*).)
>
>Now it's known that the languages recognized by regular expressions are the
>same (and in fact, effectively the same) as those recognized by finite
>automata; but it's easy to complement the language recognized by a finite
>automaton (just complement the set of accepting states.) Hence we can also
>write down a regular expression that recognizes the set of all strings not
>containing some member of S. Then all we have to do is decide whether this
>expression recognizes infinitely many strings. This is easy since it
>recognizes infinitely many strings iff it contains a nonempty expression
>followed by *.
>
>An alternate proof: let the maximal word length occurring in S be m.
>Start at the empty word, and begin producing a tree of words not containing
>any member of S by adding all possible characters at the end of the word.
>If the set of words excluding S is finite, we will eventually stop and realize
>this. If not, a node W will eventually occur in the tree such that an ancestor
>V of W has the same last m characters as V. Then if we write W=VQ,
>{V, W=VQ, VQQ, VQQQ, VQQQQ, ...} is an infinite set of words excluding S.
>
>I am sure there are much better algorithms available.
I first thought his second algorithm was transposable to polyominoes:
It looks to me like your tree algorithm for strings works just fine
when applied to snakes, resorting to some string representation of
them - the one you introduced, or more simply we can denote the moves
by E, N, W, S and the nodes by *. When examining whether a snake (A)
contains another one (B), we have to take into account several
representations of B - depending on the geometrical transformations
that map a snake onto an equivalent one (we may retain translations
and/or rotations and/or reflexions), and for each position there are
two descriptions, one starting at each end of the snake. The same
transformations should be considered while developping the snake
tree :) Anyway, these are only details which are easily managed, my
point is that the key idea of the algorithm remains valid; in short:
developping the tree until it can't be developped any more - it is
finite - OR we run accross some node w such that w=vquq and vq is an
ancestor of w and the length of q is the same as that of the longest
snake in the family. Therefore we're left with yet another complexity
problem.
What do you think?
David Moews answered:
>I agree that congruences changing the string representation of a snake
>pose no problem (I did not mention these earlier because I was not sure
>whether you were considering a polyomino as containing congruent images
>of its subpolyominoes or not.) Unfortunately there is a larger problem,
>because of the fact that some strings which seem to represent snakes
>in fact self-intersect. For example, suppose we wish to find all snakes not
>containing any polyomino congruent to a member of the following set S:
>
> ** *
>** *** ****
> *
>
>There are infinitely many strings not containing the string representation of
>these snakes: in fact, any initial segment of
>
>*E*E*N*N*W*W*S*S*E*E*N*N*W*W*S*S*E*E*N*N*W*W*S*S*.... (to use your notation)
>
>is OK. However, these strings do not correspond to infinitely many snakes,
>because unless an initial segment of the above string is sufficiently short,
>it self-overlaps, so, in fact, the only snakes avoiding S are subpolyominoes of
>
>***
>* *
>*** . For a more difficult example, take S' to be
>
> ** * *
>** *** **** ***** ;
> * *
>
>then any string of the form
>
>(*E)^a (*N)^b (*W)^c (*S)^d (*E)^e (*N)^f ... (a,b,c,d,e,f,... in {2,3})
>
>would seem to be OK (where (T)^i denotes i repetitions of the string T),
>but again there are only finitely many snakes avoiding S'.
>--
I answered:
I think we are left with two main problems:
1) Designing an algorithm to find out whether, given a polymino P, a node n on P, and a snake S, we can attach a infinite series of instances of S to n which has got n as only intersection with P;
2) Proving that, if there are infinitely many polyminos avoiding the target set, then there are two snakes V and Q such that the polyminos {V, VQ, VQQ...} are indeed snakes avoiding the target family.
Given an excluding snake W ending with the same last n moves as one of its ancestor V (W=VQ), we could check whether {VQ, VQQ, VQQQ...}, is a set of snakes, thanks to 1);
2) would garantee that we would eventually stumble against a proper (V, Q) pair whenever the avoiding set would be infinite.
Now, 1) looks pretty easy :
a) check whether {S, SS, SSS...} are valid snakes : they are iff SS is a snake;
b) (if a) holds) consider PS, PSS, PSSS... until you obtained a intersection OR the [city block] distance of each node of the (n+1)th instance to each node of P is bigger than that of its counterpart in the nth instance to the same node of P (I hope that makes sense :) .
But 2) is just a personal guess... Maybe an infinite excluding set can have some sort of an odd "spiral" structure ?
That's all folks! I know it's been a bit lengthy, but if You have found
it inspiring anyway, don't hesitate to send me your suggestions.
Cheers,
Yann David
100552.1400@compuserve.com
FRANCE
NB: Since I am not a regular reader of this newsgroup,
please e-mail your answers; I'll post a summary of the interesting
ones (if any! :).
"Vous mariez pas, les filles!" - Boris Vian