# Tiling a Square Room - Algorithm

This topic is 1826 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok guys this was a little difficult for me to figure out. So I would like someone to help me solve this puzzle.

Basically with have a square room (array) whose sides size are m = 2^n (where n any number). For example 2x2, 4x4, 16x16.

What we have to do is fill this room with ? tiles (if we delete from a 2x2 square an 1x1 square).

I have to find an algorithm and prove that any square room can be filled with these ? tiles leaving only one 1x1 square unfilled.

This algorithm has to work no matter where we decide this 1x1 square to be unfilled.

So lets say that this square will be on A(j,k) = t. Where A is the mxm array, j and k the coordinates of the unfilled 1x1 square and symbolise it with t.

So the user is going to set the place where this unfiled 1x1 square will be.

The other ? tiles will be symbolised with 1,2,3,4...ect.

Sorry for my English.

The algorithm looks like can be made as rectroactive.

##### Share on other sites

For example. A = 4x4, t = A(1,2).

It will be like this:

##### Share on other sites

Well 22n - 1 is divisible by 3 always so that's a start

Maybe you should ask in the maths forum since this is combinatorics (homework? )

EDIT: Although in combinatorics it's normally easier to prove something is impossible than to prove something is possible, numbers grow pretty fast in combinatorics.

##### Share on other sites

It is optional homework and we get bonus points for it (nobody has solved it yet).

Alvaro: I have thought of what you said.

But if the A = 16x16 I think we are going to have 4 empty 1x1... Because each link of 4 pair of 4x4 squares leave us with 1 empty 1x1.

Edit:I got it wrong. If A = 16x16 we are going to have 4 pairs of 8x8 squares.

But  in your case the empty 1x1 is going always to end up on the corner of 8x8.

What do we if the empty space is not in a corner. But somewhere inside?

##### Share on other sites

What do we if the empty space is not in a corner. But somewhere inside?

It's not somewhere inside. Notice that I changed the proposition to a stronger one, which is that you can always make the empty space be at a corner. The stronger proposition is actually easier to prove, and it implies the one you are trying to prove.

By the way, it would be dishonest of you to claim the extra credit for work I did. If you do present my work, please give me credit.

##### Share on other sites

Perhaps this diagram helps:

0 1 2 2 7 7 9 9
1 1 5 2 7 A A 9
3 5 5 4 6 6 A 8
3 3 4 4 L 6 8 8
B B C L L G H H
B F C C G G K H
D F F E I K K J
D D E E I I J J

##### Share on other sites

[duplicate because of server error]

Edited by Álvaro

##### Share on other sites

take a look at this. If the empty 1x1 was on:  4,3

1 1 2 2 7 7 9 9
1 5 5 2 7 A A 9
3 5 4 4 6 6 A 8
3 3 0 4 L 6 8 8
B B C L  L G H H
B F C C G G K H
D F F E I K K J
D D E E I I J J

##### Share on other sites

I have explained this already, but I'll do it in more detail this time. Forget for a minute what you want to prove. What I want to prove is that you can always tile the room leaving one empty spot at a corner.

So now follow the proof I posted for my theorem, not the one you want. Once you are satisfied that my proof is correct, you can see that your theorem is a corollary of mine.

Is it clear now?

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
634135
• Total Posts
3015754
×