Divide and conquer algorithm for tromino puzzle

broken image

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. It takes three clicks to place a tromino piece on the board: click on three adjacent squares in sequence. The applet below helps you test your understanding of the theorem by tiling the board manually. The proof does exploits other special cases. Although 5 appears as an exceptional case in the theorem, the 5×5 board with a removed corner can be tiled and plays an important role in the proof. Some 5×5 deficient boards can be tiled, others cannot. (The board is deficient if one of the small unit squares is missing.) If n ≠ 5, then a deficient n×n board can be tiled with L-trominoes if and only if n is not a multiple of 3.

broken image

I-Ping Chu and Richard Johnsonbaugh extended Golomb's result to squares with sides not necessarily a power of 2. Golomb's proof of the theorem became a model of elegance in elementary mathematics. Golomb gave an inductive proof to the following fact: any 2 n×2 n board with one square removed can be tiled by right (or L-) trominoes - a piece formed by three adjacent squares in the shape of an L.

broken image