The Perfect Clear Finder is a Java program that tries to place pieces in a way that results in an empty board. You specify the starting playfield & the piece sequence and the program does the rest. It can handle Hold, Soft Drop and Wall Kicks. The program won't display all possible solutions. Instead, it will show all solutions that differ in either the piece left on hold (grouped in different windows) or the location where the last piece was placed. Start the program by double clicking PerfectClear.bat .

Download:  PerfectClearFinder.zip ( 127.77k ) Number of downloads: 7260

Video:


Limitations
The Perfect Clear Finder can find all solutions of a 4-lines-perfect clear within two minutes or less ... provided it has enough virtual memory (RAM) at its disposal. With lots of J,L,T pieces at the start of the piece sequence it may need more than 1 Giga Byte of memory (with hold there'll be millions of different playfields after 5 placed pieces that may still end up in a 4-lines-perfect clear). So, the Perfect Clear Finder's speed is its strength (in relation to how difficult the actual problem is), but its need for memory is its weakpoint. I cannot guarantee that the program is terminating for a sequence longer than 10 pieces or a matrix higher than 4 rows. Therefore, there's an option to limit the amount of playfields created per ply, but in this case the program may not find all perfect clears. Also note, that the program was tested in a 32-bit environment. For 64-bit Java, it may need even more memory (because a object reference is 8 bytes there instead of 4 bytes). The Batch files (*.bat) will look like java -jar -Xms256M -Xmx1024M whereas -Xms specifies how much memory the program gets at the start and -Xmx specifies how much memory it can use at maximum.

About
The Perfect Clear Finder uses breadth first search. All fields of a ply are stored in a queue. The program processes the queue: for each field in the queue, it tries to place the current piece (or hold piece) in all possible locations (that fullfil the height limitation) and saves the resulting playfields in the next queue. If a playfield was found before, it isn't saved again: The program uses a height-balanced binary search tree to sort the found playfields such that it can swiftly say if a field is already in the next queue or not (e.g. for 1 million stored fields, the program needs only 20 or 21 comparisons). To reduce the memory usage as much as possible, the playfield was encoded in 8 short variables and the queue as a Vector. To reduce the number of saved fields, the program also checks for barriers that spit the field in 2 parts with number of empty cells not divisible by 4 (2 adjacent columns form a barrier if for each row there's at least one filled cell in those 2 columns).

The Perfect Clear Finder™ was brought to you by Download More RAM - get more RAM for free!

Wow, you really went above and beyond on this one. Very thorough and very useful. Thanks for making this.

Dang, this is head and shoulders above your last version!

Awesome program Misstake! I love the multiple solutions and high customization it provides, this is truly fantastic

Wow, this is great. Thanks for sharing!

Coolest thing to ever have happened since Belzebub's Nullpomino things.
Great job Misstake, this is awesome.

Thanks, guys!

okkidokki quality posts always 100%
I've seen the japanese use it

you're amazing okkidokki

Bump

there seems to be a little bug.. found when i'm trying it with sega tetris' power-on pattern.

choose pc after 8 rows, limit to 1000000 fields (to let it finish), hold=off and softdrop=off (don't know whether it's related), input whatever sequence, let it run, it successfully calculates to the end, but seems to get problem generating and presenting the solution list. it prints a block of exception in the console window, arrayindexoutofboundexception i remember..

yeah so how about adding real sega tetris rotation and doing a brute-force solution for sega tetris?

http://www.geocities.jp/arcadon765/tetris.html
http://www.geocities.jp/tetris_denpa/index.html

I was able to reproduce that bug. I have set the maximum sequence length to 15 or 16 in the visualizer (NUM_TURNS = 15). I will fix it sometime and probably also add Sega rotation system (I guess that also means changing the kick-table to TGM if selecting Sega).

sega tetris has no kicks at all, and only CCW rotation.

Hey Okey, I've been working off and on on a project to document every possible solution for clearing fixed spaces, beyond just the scope of the standard 4x10 PCs; I'm also looking into possibilities for fields 4x5 thru 4x9.

How hard would it be to create a separate, modified version of your PC finder for these other field sizes? :-S

It's possible but it takes some effort. For a 9 columns wide matrix you can also fill the most left column with blocks (or most right).

Is that the case with 4x5, 4x6, 4x7 and 4x8 as well?

If it's too much work or not worth the effort, I would totally understand. If you do decide to make time to do it, I can't even begin to think of how I could thank you.

The reason I'm asking is because I'm building a Tetris curriculum for kids, and having something that can calculate these possibilities would be a great tool in my pool of resources.

I'll probably do it but I don't have the time in the next few days.

Also: There's a Tetris Puzzle Flash game with the goal to do perfect clears. You can decide in which order the pieces appear. No softdrop though and every placement must clear a line.