Tromino Tiling Puzzle

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

One or more copies of the  6 given shapes have been used to tile the grid and then the outlines were removed.  Can you fill them in again?

Background & Techniques

The 6x6 grid at right was tiled using only the two "tromino" shapes and their rotations. (Four orientations for the "L" shape and two for the "I"). Use as many of each tromino as needed. The locations of the tromino dots are shown on the grid but without the outlines.


This initial version of the program does not support user play, so, for now, you'll have to print or copy this screen to work on solving the puzzle for yourself. 

The Search button on the program form animates the program solving the puzzle by "trial
and error". Tiles are placed from left to right and top to bottom, trying all six tile versions in succession and backtracking when we reach a dead end. I've inserted a 1 second delay after each placement or retraction so you will be able to follow the process. By coincidence there is only one location near the bottom of the grid
where the first tromino which can be placed is not the correct one and the program must backtrack and replace it a few steps later.

Source: "Mensa "Puzzle Calendar" for May 5, 2014.


Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

An early step any program development project is determining the data structures which will model the puzzle elements.  For a puzzle or game which is played on a 2 dimensional board or grid, I routinely let a TStringGrid control represent it.  StringGrid cells contain string data but can also have more complex objects associated with the via the Objects property.  In this case, I chose a string structure to represent  tromino and cell contents.  Trominoes are 2x2  string arrays for the four 'L' trominoes, and 1x3 and 3x1 arrays for the 'I' trominoes.  Grid and tromino cells strings are 6 characters in length defined as follows:

Position  Contents,
1 ' ' = Display blank, 'D' = display a centered dot , (For a tromino definition '_' = unused corner of the 2x2 tromino.  
2 '0' = cell unassigned, '1' through '6' = contains a cell of tromino type 1 through 6
3 '1' = draw top edge, '0' no top edge
4 '1' = draw right edge, '0' no right edge
5 '1' = draw bottom edge, '0' no bottom edge
6 '1' = draw left edge, '0' no left edge

  

"Recursive Search with Backtracking" is a systematic search technique which takes advantage of the fact that placing a piece on the board is pretty much the same for each piece placed.  In this case, function PlacePiece(x,y) looks for one of the six tromino shapes that will fit with its top left corner in the empty grid cell at column x and row y.  PlacePiece calls function Fits(x,y,i) which does the checking and returns "True" if tromino it fits at (x, y).    If Fit returns True then procedure Place is called to actually fill in the grid cells with the tromino definition strings. PlacePiece then finds the next unfilled cell and calls itself with with that top-left coordinate.   If PlacePiece tries all 6 trominoes and cannot find one that fits, it return false to the previous PlacePiece caller location which will the call Remove procedure to undo the piece he added and continue searching for another choice.  This is the "backtracking"  side of "recursive search with backtracking".  If PlacePiece runs out of empty cells to fill, the puzzle is solved. I returns True to the calling level which passes back up the line until answer comes back to the initial call made from the SearchBtnClick procedure.  

There were a couple of new complications in implementing the above. 

  • The search for open grid location by moving left to right and top to bottom works well except for  the reversed L tromino where the first empty cell is top-right corner rather than the top-left corner.  PlacePiece detects this condition and passes the prior column to Fits function when top-left tromino cell is unused.
  • Placed trominoes are outlined inside of cell boundaries in a DrawCell StringGrid exit.  This leaves corners unconnected drawn unless special actions are taken.  First fix was to draw extend connecting lines back into the adjacent cell by W, the "wall offset" distance.  This worked in almost all corners except when the extended border line is overwritten when that cell is drawn.  A couple of exception statements handle the two cases and replace the  previously drawn line extensions.                   

All-in-all, this was a good medium complexity project requiring about 500 lines of code and a week of spare time programming fun. 

Running/Exploring the Program 

Suggestions for Further Explorations

Add user play
.
   

 

Original:  May 14, 2014

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.