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

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:

"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. 

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

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.