Dominoes on a chessboard
Colin Barker
way that the remaining squares can be covered by N*(N-1)/2 dominoes in a
unique way?
For example, for N=8, 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-proportional font.]
--
Colin
Virgil
"Colin Barker" <colin....@wanadoo.fr> wrote:
If you remove two squares of the same color, or two more of one color
than the other, then there is no way at all of covering the remainder of
the board with dominoes.
Norbert Marrek
Sorry, but that was not the question. It is possible to remove 2 squares
from the chessboard such that the remaining squares can be covered by
dominoes.
Aloha,
Norbert
[Mr.] Lynn Kurtz
Not exactly your question, but if you put the additional condition
that each subsquare anchored at the upper left corner must itself be
filled in a unique way, the answer is yes, and it's not difficult to
see by induction. See the graphic at
http://math.asu.edu/~kurtz/usenet%20dominoes.pdf
--Lynn
Chip Eastham
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.
regards, chip
Colin Barker
98266a4a-9388-4191...@13g2000hsb.googlegroups.com...
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
Chip Eastham
> "Chip Eastham" <hardm...@gmail.com> a écrit dans le message de news:
> 98266a4a-9388-4191-bbe7-a8c87c281...@13g2000hsb.googlegroups.com...
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 shift 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 = 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
Colin Barker
--
Colin
Chip Eastham
> Thanks Chip.
> --
> Colin
I'll post a note in comp.lang.prolog about the question
that was suggested to me by your problem.
--c
hagman
Great.
Now the same task with additional requirement that the
result be connected. :)
Chip Eastham
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
Chip Eastham
Actually, we can get both the removed and the
remaining (uniquely tilable) portions 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
Colin Barker
cdd311bd-ec34-4827...@u3g2000hsc.googlegroups.com...
[snipped]
Actually, we can get both the removed and the
remaining (uniquely tilable) portions 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...
Chip,
[I don't know why the lines of your last post aren't prefixed with '>'.]
I found the following method of doing this. The diagrams show it better than
any written explanation I could give.
Even N:
--++++
+--+++
++--++
++++++
++++++
++++++
--++++++
+--+++++
++--++++
+++--+++
++++++++
++++++++
++++++++
++++++++
Odd N:
--+++
+--++
++-++
+++++
+++++
--+++++
+--++++
++--+++
+++-+++
+++++++
+++++++
+++++++
--
Regards,
Colin
Chip Eastham
> "Chip Eastham" <hardm...@gmail.com> a écrit dans le message de news:
> cdd311bd-ec34-4827-84da-41b435827...@u3g2000hsc.googlegroups.com...
Yes, exactly! Start at a corner and take
N zigzag steps (alternating row and column).
regards, chip