Jump to content
  • Advertisement
Sign in to follow this  
shadowstep00

Tiling a Square Room - Algorithm

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

If you intended to correct an error in the post then please contact us.

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.

 

Thanks in Advance!!!

Edited by shadowstep00

Share this post


Link to post
Share on other sites
Advertisement

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

 

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

 

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.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites

It is optional homework and we get bonus points for it tongue.png (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?

Edited by shadowstep00

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Edited by shadowstep00

Share this post


Link to post
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!