View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Tiling a Square Room - Algorithm

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

13 replies to this topic

Posted 19 January 2014 - 10:53 AM

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.

Edited by shadowstep00, 19 January 2014 - 11:04 AM.

Failure is not an option...

Posted 19 January 2014 - 11:00 AM

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

It will be like this:

Failure is not an option...

Posted 19 January 2014 - 12:21 PM

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.

Edited by Paradigm Shifter, 19 January 2014 - 12:25 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#4Álvaro  Members

Posted 19 January 2014 - 12:35 PM

POPULAR

I think in this case it's easier to prove a slightly stronger statement: You can always do it leaving a corner as the empty square.

Proceed by induction: For 1x1 it's obvious (or if you want to start at 2x2, it's still obvious).

Now if you want to tile a room of size 2^(n+1) x 2^(n+1), divide it in 4 square parts and use the induction hypothesis to leave one corner empty in each piece. Since you can rotate any configuration to get another valid configuration, you can choose which corner to leave empty in each case. For three of the pieces you can leave the corner that is in the inside of the room (so you can fill those three squares with one piece), and for the other one pick a corner of the room. Presto!

The proof above is constructive, so you can turn it into a recursive algorithm pretty easily.

Edited by Álvaro, 19 January 2014 - 12:36 PM.

Posted 19 January 2014 - 12:41 PM

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?

Edited by shadowstep00, 19 January 2014 - 01:09 PM.

Failure is not an option...

#6Álvaro  Members

Posted 19 January 2014 - 02:38 PM

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.

#7Álvaro  Members

Posted 19 January 2014 - 02:46 PM

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

#8Álvaro  Members

Posted 19 January 2014 - 02:48 PM

[duplicate because of server error]

Edited by Álvaro, 19 January 2014 - 02:48 PM.

Posted 19 January 2014 - 02:54 PM

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, 19 January 2014 - 02:54 PM.

Failure is not an option...

#10Álvaro  Members

Posted 19 January 2014 - 02:58 PM

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?

#11TLH14  Members

Posted 19 January 2014 - 03:16 PM

A 2x2 room is easily filled as, once the empty square is allocated, the mere remainder of the room makes up a single tile. As you can see from this picture, an empty square can also fit into any 4x4 pattern and it is that top-leftmost 4x4 pattern (herein referred to as the TL pattern) that is key for filling any size room.

In this example, the empty square has a coordinate of (2,5) in an 8x8 room. Once the first 4x4 pattern was found, the TL pattern from the previous image was wrapped around it and the pink tile filled in what was left. Another way of looking at the process (I'm unsure as to which is more efficient for an algorithm) is the pink tile being placed on the corner of the 4x4 pattern (this corner is also the center of the room; in larger rooms this corner is at the center of a subsection of the room), followed by the TL pattern wrapping around the pink tile.

The following process illustrates how to fill a 32x32 room with an empty tile coordinate of (2,19):

Divide the room into fourths and find which fourth the empty square occupies...

Divide that fourth into fourths and find which of those fourths (a sixteenth of the whole room) the empty square occupies...

Repeat that process, finding the empty square's position in a fourth of that sixteenth (a sixty-fourth of the whole room)...

Finally, find the empty square in a fourth of the sixty-fourth (a two hundred fifty-sixth of the whole room).

The reasoning behind finding the empty square's position relative to fourths is that the room is filled via an inverse process. You might find it more streamlined to simply find the empty square in a two hundred fifty-sixth from the start, but the room is still filled by fourths:

You take the empty square and generate a 4x4 pattern around it. This can be done similar to the 8x8 example above. The remainder of the two hundred fifty-sixth that the empty square occupies becomes a tile, then you wrap a 2x2 pattern around that with empty spaces becoming a tile (or have a tile attach itself to the corner of the two hundred fifty-sixth [which corner is determined by being in the center of a sixty-fourth] with other tiles generating around that tile).

From there, you repeat whichever process you use to generate an 8x8 square, followed by a 16x16 square, until you fill the whole 32x32 room.

This process can be used to fill any sized room presented in your problem, but unfortunately I am not so mathematically minded as to translate this process into an algorithm.

(P.S. All of the images in this post were created using MS Paint, so you can take your Photoshop and shove it. )

#12Álvaro  Members

Posted 19 January 2014 - 03:40 PM

OK. I misread the original post, so my proof has to be adapted.

The statement is that we can tile any 2^n x 2^n room leaving only a designated square empty.

We proceed by induction, as before. The designated square is in one of the four 2^(n-1) x 2^(n-1) squares, and we know we can tile that square leaving any 1x1 square we want empty because of the induction hypothesis. For the other three 2^(n-1) x 2^(n-1) squares, tile them leaving the 1x1 square at the middle of the room empty, and then add a tile in the middle covering the three empty spots thus created.

Again, this is easy to implement as a recursive function.

Edited by Álvaro, 19 January 2014 - 03:41 PM.

Posted 23 January 2014 - 04:39 AM

First of all thank you guys for helping me so far!

I have been trying to figure out how to implement this recursive algorithm.

But I have so liitle experience on recursive algorithms that I can't figure out how to start.

This is what I am trying to implement right now...

First the algorithm is gonna seperate the array to fourths till it simplifizes it enough to find the empty space just like Anastas said.

Then its going to begin filling the fourths one by one till the end.

So...

First the division

Then we start filling the fourths one by one.

First

Second

Last

Sorry for replying so late. But I was busy the last 2-3 days.

Edited by shadowstep00, 23 January 2014 - 04:40 AM.

Failure is not an option...

#14Álvaro  Members

Posted 23 January 2014 - 07:50 AM

The way recursion works, you write a function that performs the total task or any of the smaller tasks in which it can be decomposed.

The first thing to figure out is what parameters the function should take (i.e., what describes one of the tasks). In this case, a tasks is "tile the 2^n x 2^n square whose top-left corner is at top_row and left_column and which leaves empty the square at empty_row and empty_column". So you need to pass parameters n, top_row, left_column, empty_row and empty_column.

The next thing to figure out is when the process stops, which is usually the first thing the function will check. You can do something like "if n is 0, there's nothing to do".

You then figure out how to decompose the task you are given into smaller subtasks, and call the function recursively with each subtask.

Give that a try.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.