Announcement: Be excellent to each other.


Caravel Forum : Other Boards : Anything : Tetris-tiling the square
New Topic New Poll Post Reply
Poster Message
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Tetris-tiling the square (+1)  
In this problem, you are given a square grid of spaces (with some spaces colored and some not).



The goal is to fully tile the grid with tetrominoes (with no overlap).

Tetrominoes (Tetris pieces) are always green, yellow, or blue exactly as depicted here. Green means that piece segment is attached to the rest of the piece on 1 of its sides, yellow 2 sides, and blue 3 sides. Pieces can be rotated and/or reflected.



A color on the grid means the piece segment there must match the color. White matches any color.

Solution:


____________________________
34th Skywatcher

[Last edited by disoriented at 12-27-2014 12:44 AM]
12-27-2014 at 12:36 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
Now solve this grid:



Can this be modeled as an Exact Cover problem?

____________________________
34th Skywatcher
12-27-2014 at 12:41 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Kallor
Level: Master Delver
Rank Points: 276
Registered: 04-02-2007
IP: Logged

File: AdZbdyY.png (6.4 KB)
Downloaded 12 times.
License: Public Domain
icon Re: Tetris-tiling the square (0)  
Fun!

I'd say the problem directly satisfies the definition or exact cover problem. That is, X is the grid and S consists of those tetris blocks that do not violate any of the colorings given in the beginning.

http://en.wikipedia.org/wiki/Exact_cover

____________________________
Kallor
12-27-2014 at 01:27 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
Well done.

Did you write a solver, or do it via deductions and guesses?

____________________________
34th Skywatcher

[Last edited by disoriented at 12-27-2014 06:27 PM]
12-27-2014 at 06:26 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Kallor
Level: Master Delver
Rank Points: 276
Registered: 04-02-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
I used deduction, mspaint is pretty convenient for making a hypothesis, string of deductions and undoing everything after a contradiction.

I guess you could write a solver using this Knuth's Dancing links algorithm advertised on Wikipedia.

____________________________
Kallor

[Last edited by Kallor at 12-27-2014 07:00 PM]
12-27-2014 at 06:56 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
For DLX, I'd guess you'd have a constraint column in the matrix for each square being filled, and then each colored square being satisfied? How would your rows be structured? It seems like you'd need a row for every possible placement of tiles.

____________________________
34th Skywatcher
12-27-2014 at 07:17 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Tetris-tiling the square (0)  
A row would be a placement of any tile in any location that satisfies the colouring. Columns would just be whether each square is filled.
12-27-2014 at 07:53 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Kallor
Level: Master Delver
Rank Points: 276
Registered: 04-02-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
I'm not really that good a programmer (yet ;) ), so the stuff about doubly linked lists was too much for me. But using the notations used in the Knuth's Algorith X page

http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

instead of the Dancing links page

http://en.wikipedia.org/wiki/Dancing_Links

we have a column for each tile of the grid (16 in your first example), and a row for each possible tetris tile not violating any constraint given by the initial colors (I think it's 7 in your first example).

____________________________
Kallor
12-27-2014 at 08:00 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
How did you calculate 7? I guess this is the part I don't understand yet.

____________________________
34th Skywatcher
12-27-2014 at 08:16 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Tetris-tiling the square (0)  
There are 7 valid ways of placing a tetromino on that 4x4 grid satisfying the colouring (the L can go in 3 spots; the S can go in 2 spots; the T can go in 2 spots). You want to choose some of those 7 options in a way that covers every square exactly once.
12-27-2014 at 08:20 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged

File: BlankGrid.png (14.4 KB)
Downloaded 813 times.
License: Public Domain
icon Re: Tetris-tiling the square (0)  
quote:
There are 7 valid ways of placing a tetromino on that 4x4 grid satisfying the colouring (the L can go in 3 spots; the S can go in 2 spots; the T can go in 2 spots). You want to choose some of those 7 options in a way that covers every square exactly once.

Is there an efficient way of precomputing that number of placements in large grids? Or is it something you just go through one at a time (somehow)?

(P.S. Here's a 12x12 puzzle)
Click here to view the secret text


____________________________
34th Skywatcher

[Last edited by disoriented at 12-27-2014 08:29 PM]
12-27-2014 at 08:26 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Tetris-tiling the square (0)  
It's just a case of trying each option - for each tetromino rotation/reflection, for each location on the grid, if the colours match, add a row to the matrix.

This part wouldn't take any time at all on a computer; for a 12x12 grid there are under 144 possible locations of 19 different tetrominoes.
12-27-2014 at 08:33 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Kallor
Level: Master Delver
Rank Points: 276
Registered: 04-02-2007
IP: Logged

File: D0jTcaC.png (11.5 KB)
Downloaded 9 times.
License: Public Domain
icon Re: Tetris-tiling the square (0)  
By hand (in the attached image: any other tetris tile would violate some initial colors). In a computer program, you would naturally need to make a little loop checking what tetris tiles are possible. Considering the algorithm is slow anyways this is not serious complexitywise: it's only something like n (the number of tiles) x 19 (the number of different tetris blocks taking orientations into account) x 4 (tiles in a tetris block) if-statements.

EDIT: ... and another post clash with TripleM. You are fast, man! MORE EDIT: And also right, no reason to multiply with the 4.

____________________________
Kallor

[Last edited by Kallor at 12-27-2014 08:39 PM]
12-27-2014 at 08:33 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
Hmmm... 19 configurations, got it!

Here's the algorithm I'm going to try to implement:

search(grid)
{
  let s = first unfilled square starting from upper left (scanning across then down)

  if s is null
  {
    // grid solved
    print solution
  }
  else
  {
    for (each of the possible configurations*)
    {
      if configuration fits in the grid without overlapping another placed piece or grid edge, and doesnít conflict
      with grid numerical constraints in 4 grid squares
      {
        place piece P there (in all 4 grid squares)
        search(grid)
        remove piece P (backtrack)
      }
    }
  }
}


(Instead of this recursive searching, would it be significantly faster to add a row to the DLX matrix for each placement and then run DLX?)

____________________________
34th Skywatcher

[Last edited by disoriented at 12-29-2014 02:03 AM]
12-29-2014 at 01:27 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
*Configurations

piece L : 4 ways
backwards piece L : 4 ways
piece S : 2 ways
backwards piece S : 2 ways
straight piece : 2 ways
square piece : 1 way
T-piece : 4 ways











____________________________
34th Skywatcher

[Last edited by disoriented at 12-29-2014 01:55 AM]
12-29-2014 at 01:29 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Tetris-tiling the square (0)  
That may well work reasonably fast. Other than the concept of the data structure, that algorithm would run the same sort search that DLX does, but with one big exception - it doesn't use the "S heuristic". That's what provides the biggest speedup in running time, so DLX would still run significantly faster.

As an example, there could be a huge number of valid ways to cover the top portion of the board. You would need to loop over every single one before seeing what result that has on the lower half. DLX may instead find a special area elsewhere on the board which has a much more limited number of options; placing these tetrominoes may result in other forced placements cascading back into the top of the board, immediately ruling out virtually all of the options you had been trying at the start. DLX with the S heuristic will always find the best area of the board to work on.

(This is similar to what happened with the Greco Latin squares when you tried solving one latin square first. There might have been a huge number of ways of completing that square, so your algorithm would have checked them all - DLX did both squares at once.)

[Last edited by TripleM at 12-29-2014 02:39 AM]
12-29-2014 at 02:36 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
quote:
"S" heuristic

Is that the same heuristic as choosing the lowest numbered column in the matrix?

____________________________
34th Skywatcher
12-29-2014 at 03:57 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Tetris-tiling the square (0)  
Lowest as in the column with the least 1s, yes. (Ie the square in the grid that has the least number of ways to cover it in a valid way.)

[Last edited by TripleM at 12-29-2014 04:28 AM]
12-29-2014 at 04:28 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
:thumbsup

____________________________
34th Skywatcher
12-29-2014 at 05:34 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1361
Registered: 02-05-2003
IP: Logged
icon Re: Tetris-tiling the square (0)  
Here's a comparison of running times of the two methods in seconds - both using my DLX code but one using the S-heuristic, and one just filling the top left square at each stage:

4x4 puzzle: 0.004 vs 0.004
10x10 puzzle: 0.050 vs 1.523
12x12 puzzle: 0.301 vs 11.640

It's a factor of 30 to 40 times faster.
12-29-2014 at 07:05 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
quote:
TripleM wrote:

It's a factor of 30 to 40 times faster.


Thatís quite interesting!

____________________________
34th Skywatcher
12-29-2014 at 11:16 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
disoriented
Level: Smitemaster
Rank Points: 1201
Registered: 08-07-2007
IP: Logged
icon Re: Tetris-tiling the square (0)  
Extending the problem

____________________________
34th Skywatcher
12-30-2014 at 01:12 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Other Boards : Anything : Tetris-tiling the square
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.