On Apr 1, 5:26 am, "Colin Barker" <colin.bar...@[EMAIL PROTECTED]
> wrote:
> "Chip Eastham" <hardm...@[EMAIL PROTECTED]
> a =E9crit dans le message de news:
> 98266a4a-9388-4191-bbe7-a8c87c281...@[EMAIL PROTECTED]
>
>
>
> > On Mar 29, 12:32 pm, "Colin Barker" <colin.bar...@[EMAIL PROTECTED]
> wrote:
> >> Is it always possible to remove N squares from an NxN chessboard in
suc=
h
> >> a
> >> way that the remaining squares can be covered by N*(N-1)/2 dominoes
in =
a
> >> unique way?
>
> >> For example, for N=3D8, there is only one way of covering the
following=
> >> board,
> >> where '-' represents a removed square, and '+' represents a remaining
> >> 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
fac=
t
> 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
uniqu=
e
> 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
|
