Re: covering a grid with dominos

On Wed, 27 Jul 2005 14:32:46 +1000, Gerry Myerson
<gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

>In article <a79ee1pg7dg8aee610nk099lr8e47dqgk2@xxxxxxx>,
> quasi <quasi@xxxxxxxx> wrote:
>
>> By a grid we will mean, as above, an m x n rectangular grid with a
>> specified subset of cells removed.
>>
>> A cell can be identified by its cell address so cell (i,j) refers to
>> the cell at row i, col j.
>>
>> Call the cell (i,j) "even" or "odd" according as i + j is even or odd.
>>
>> A grid will be called block connected if from any cell there is a
>> "block path" to any other cell, where by a block path we mean a
>> sequence of 1x1 cells in the grid such that successive cells in the
>> path share a common edge. So for example, a 2 x 2 grid with the cells
>> on the main diagonal removed is not block connected. For the warm up
>> problems, all the grids were block connected except the grid for
>> problem 2.
>>
>> It's easy to show:
>>
>> Given a block connected grid, if the grid can be covered by dominos
>> then the number of even cells must equal the number of odd cells.
>>
>> I conjecture the converse:
>>
>> If a block connected grid has an equal number of even and odd cells
>> then it can be covered by dominos.
>>
>> I believe the conjecture is true, but I haven't really tried the
>> problem.
>>
>> Perhaps it's not true and there's a simple counterexample, or maybe
>> it's true but well known -- I really don't know.
>>
>> In any case, I thought I'd pose it as a problem to the group.
>
>xxox
>oooo
>xoox
>xxox
>
>This is a 4 x 4 grid with the cells marked x removed.
>The remaining cells, marked o, are 8 in number, 4 even, 4 odd.
>They are block-connected.
>It's easy to see that they can't be covered by dominos.

That was fast. Well, so much for that conjecture.

So now the problem is to find a simple condition that is necessary and
sufficient for a block connected grid to be coverable.

quasi
.

Relevant Pages

  • ANN: TAdvStringGrid v3.0 released
    ... We're excited to announce the release of the new TAdvStringGrid v3.0 at ... copies grid as HTML on the clipboard ... Support for background display over full background, ... Filter selection to filter on virtual cell text or grid cells text ...
    (borland.public.delphi.thirdpartytools.general)
  • ANN: GridPack V2.0 for ReportBuilder - now better than ever !!!
    ... package: TrbCrossTab and TrbPageBreak. ... Grid Pack for ReportBuilder is a set of components designed ... to work with ReportBuilder, the report tool from Digital Metaphors, ... - Cells can be stretch. ...
    (borland.public.delphi.thirdpartytools.general)
  • covering a grid with dominos
    ... cells, with a specified subset of cells removed, and an unlimited ... supply of dominos, the problem is to determine whether the grid can be ...
    (sci.math)
  • Re: GridPack V2.0 for ReportBuilder - now better than ever !!!
    ... > to work with ReportBuilder, the report tool from Digital Metaphors, ... > TrbTableGrid is a stretchable table grid, ... > - Cells can be merged and split. ... > - All the features of TrbTableGrid, plus, ...
    (borland.public.delphi.thirdpartytools.general)
  • Re: Dungeon via Particle Aggregation Algo
    ... Draw a corridor between one of the existing rooms and selected cell ... If for example, you draw a room, and then use that room as the next center point, you would probably end up with a winding passage of rooms resembling a random walk along the grid. ... This method, as well as the bsp method, could be considered cousins in this respect, in that both are working within a grid of cells to define the working space of the dungeon. ... On a theme level you may have a central temple, a secondary temple, a hidden treasure room, some crypts, a prayer room, etc. ...
    (rec.games.roguelike.development)