On Apr 7, 11:01 pm, Chip Eastham <hardm...@[EMAIL PROTECTED]
> wrote:
> On Apr 7, 7:37 am, hagman <goo...@[EMAIL PROTECTED]
> wrote:
>
>
>
> > On 2 Apr., 15:24, Chip Eastham <hardm...@[EMAIL PROTECTED]
> wrote:
>
> > > On Apr 1, 5:26 am, "Colin Barker" <colin.bar...@[EMAIL PROTECTED]
> wrote:
>
> > > > "Chip Eastham" <hardm...@[EMAIL PROTECTED]
> a =E9crit dans le message de
new=
s:
> > > >
98266a4a-9388-4191-bbe7-a8c87c281...@[EMAIL PROTECTED]
>
> > > > > On Mar 29, 12:32 pm, "Colin Barker" <colin.bar...@[EMAIL PROTECTED]
>
wrot=
e:
> > > > >> Is it always possible to remove N squares from an NxN
chessboard =
in such
> > > > >> a
> > > > >> way that the remaining squares can be covered by N*(N-1)/2
domino=
es in a
> > > > >> unique way?
>
> > > > >> For example, for N=3D8, there is only one way of covering the
fol=
lowing
> > > > >> board,
> > > > >> where '-' represents a removed square, and '+' represents a
remai=
ning
> > > > >> square:
>
> > > > >> -+++++++
> > > > >> +-+-++++
> > > > >> ++++-+++
> > > > >> ++++-+++
> > > > >> +++++-+-
> > > > >> ++++++++
> > > > >> ++++++++
> > > > >> ++++++-+
>
> > > > >> [This would look better using a non-pro****tional font.]
> > > > >> --
> > > > >> Colin
>
> > > > > Have you considered posting this problem to comp.lang.prolog?
> > > > > It suggests to me the question of how best to require that a
> > > > > solution is unique.
>
> > > > Chip,
>
> > > > This chessboard configuration, and many others with N up to 10,
was =
in fact
> > > > generated by a (Visual) Prolog program. The program generates
random=
> > > > chessboards having the appropriate number of missing white and
black=
> > > > squares, and then uses an exact cover technique to see if there is
a=
unique
> > > > solution.
> > > > --
> > > > Colin
>
> > > Hi, Colin:
>
> > > Yes, it is always possible to remove N squares from an
> > > NxN checkerboard such that the remaining squares can be
> > > uniquely tiled with dominoes.
>
> > > As you know, for N even we need to remove an equal
> > > number of squares of both colors, and for N odd we
> > > need to remove one more of the color of the corner
> > > squares than of the other color.
>
> > > Here's a recipe that produces a unique tiling both
> > > for even and odd N. Take the N diagonal squares,
> > > and ****ft the lower "half" floor(N/2) squares over
> > > by one column. Clearly this divides the board into
> > > two separate regions, and each of these regions can
> > > be viewed as consisting of two adjacent "stepped"
> > > regions in which tiling is forced by the boundary
> > > (with a bit of degeneracy for N < 4).
>
> > > Here's a diagram for N =3D 6:
>
> > > X * * * * O
> > > O X * * O O
> > > O O X O O O
> > > O O X O O O
> > > O * * X O O
> > > * * * * X O
>
> > > regards, chip
>
> > Great.
> > Now the same task with additional requirement that the
> > result be connected. :)
>
> Would you believe... simply connected? At least if
> you are asking about the region tiled by dominoes.
>
> Start in one corner on the top edge of the board and
> remove every other square. Along the bottom edge of
> the board, for N even remove corresponding squares in
> the same columns for a total of N, N/2 of each color,
> and for N odd remove the squares of complementary
> columns for a total of (N+1)/2 of the corner color
> and (N-1)/2 of the other color.
>
> * * * * * * *
>
> It seems true that removal of N squares is needed
> to provoke a unique tiling of the remaining board.
> But beyond showing this for pitifully small special
> values of N, I have no idea how to prove it.
>
> --c
Actually, we can get both the removed and the
remaining (uniquely tilable) ****tions of the
board to be simply connected. I'll leave this
as a challenge for now.
Still no idea how to prove that N removed squares
are necessary to provoke the unique tiling...
--c
|
