The Puzzle:
You are given an (8 x 8) grid (i.e. 8 rows, 8 columns) and an infinite supply of (1 x 3) tiles. You have to find a tilling of this grid with these (1 x 3) tiles such that, exactly 1 cell is left uncovered. Note that, you can rotate some of the tiles if you wish.
The Solution: It's an easy puzzle actually!
A Question: ( this is the actual puzzle! )
Is it always possible to solve the puzzle, if the position of the uncovered cell is specified ?
Answer: I don't know.
I think you can check it by writing a program. Check if the following dynamic programming solution will work or not -
ReplyDeleteif we start to fill up from top (both vertically and horizontally), in a particular row, for each column there can be one of the 3 options -
1. It doesn't have any tile
2. It have a tile but that does not extend any lower
3. It have a tile and that extends one cell down
We can now place more tiles from this position. Total number of states will be 8 x 3^8.
The source of this problem asks for a mathematical proof of the yes/no answer!
ReplyDeleteBut still, I think I would resort to that DP solution you mentioned to know the yes/no part, and then try to prove it mathematically.
Thanks vaia :)