Tiling of a $9\times 7$ rectangle

Question

Can a rectangle $9\times 7$ be tiled by "L-blocks" (an L-block consists of $3$ unit squares)?

Although the problem seems to be easy, coloring didn't help me. The general theory is interesting, but I'm looking for an elementary and relatively simple solution (suitable for a high school olympiad).

Answer 1

Here's Python code to find the solutions for this puzzle for any grid size. It outputs the solutions both as text and as PPM files. This code was tested on Python 2.6.6 but it should run correctly on Python 2.5 or any later version.

#! /usr/bin/env python

''' Knuth's Algorithm X for the exact cover problem,
using dicts instead of doubly linked circular lists.
Written by Ali Assaf

From http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
and http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt

Converted to Python 2.5+ syntax by PM 2Ring 2013.01.27

Trominoes version
Fill a rectangular grid with L-trominoes
22656 solutions for 9 x 7

See http://math.stackexchange.com/q/1580934/207316

Now with PPM output in 4 colours; graph colouring also done via Algorithm X
'''

from __future__ import print_function
import sys
from itertools import product
from operator import itemgetter

#Algorithm X functions
def solve(X, Y, solution):
    if not X:
        yield list(solution)
    else:
        c = min(X, key=lambda c: len(X[c]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            for s in solve(X, Y, solution):
                yield s
            deselect(X, Y, r, cols)
            solution.pop()

def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].remove(i)
        cols.append(X.pop(j))
    return cols

def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)

#Invert subset collection
def exact_cover(X, Y):
    newX = dict((j, set()) for j in X)
    for i, row in Y.items():
        for j in row:
            newX[j].add(i)
    return newX

#----------------------------------------------------------------------

#Solve tromino puzzle
def fill_grid(width, height):
    #A 2x2 block of grid cells
    cells =((0,0), (1,0), (0,1), (1,1))

    #Set to cover
    X = product(range(width), range(height))

    #Subsets to cover X with. All possible L-block at each grid location
    Y = {}
    for x, y, i in product(range(width - 1), range(height - 1), range(4)):
        #Turn the 2x2 block into an L-block by dropping the cell at j==i
        Y[(x, y, i)] = [(x+u, y+v) for j,(u,v) in enumerate(cells) if j != i]

    #Invert subset collection
    X = exact_cover(X, Y)

    #An empty grid to hold solutions
    empty = [[0] * width for _ in range(height)]

    keyfunc = itemgetter(1, 0, 2)
    for s in solve(X, Y, []):
        #Convert cell tuple list into grid form
        s.sort(key=keyfunc)
        grid = empty[:]
        for k, (x, y, i) in enumerate(s):
            for j, (u,v) in enumerate(cells):
                if j != i:
                    grid[y+v][x+u] = k
        yield grid

#----------------------------------------------------------------------

#Colour a graph given its nodes and edges
def colour_map(nodes, edges, ncolours=4):
    colours = range(ncolours)

    #The edges that meet each node
    node_edges = dict((n, set()) for n in nodes)
    for e in edges:
        n0, n1 = e
        node_edges[n0].add(e)
        node_edges[n1].add(e)

    for n in nodes:
        node_edges[n] = list(node_edges[n])

    #Set to cover
    coloured_edges = list(product(colours, edges))
    X = nodes + coloured_edges

    #Subsets to cover X with
    Y = {}
    #Primary rows
    for n in nodes:
        ne = node_edges[n]
        for c in colours:
            Y[(n, c)] = [n] + [(c, e) for e in ne]

    #Dummy rows
    for i, ce in enumerate(coloured_edges):
        Y[i] = [ce]

    X = exact_cover(X, Y)

    #Set first two nodes
    partial = [(nodes[0], 0), (nodes[1], 1)]
    for s in partial:
        select(X, Y, s)

    for s in solve(X, Y, []):
        s = partial + [u for u in s if not isinstance(u, int)]
        s.sort()
        yield s

#Extract the nodes and edges from a grid
def gridtograph(grid):
    gridheight = len(grid)
    gridwidth = len(grid[0])

    #Find regions.
    nodes = list(set(c for row in grid for c in row))
    nodes.sort()
    #print 'nodes =', nodes

    #Find neighbours
    #Verticals
    edges = set()
    for y in range(gridheight):
        for x in range(gridwidth - 1):
            c0, c1 = grid[y][x], grid[y][x+1]
            if c0 != c1 and (c1, c0) not in edges:
                edges.add((c0, c1))

    #Horizontals
    for y in range(gridheight - 1):
        for x in range(gridwidth):
            c0, c1 = grid[y][x], grid[y+1][x]
            if c0 != c1 and (c1, c0) not in edges:
                edges.add((c0, c1))

    edges = list(edges)
    edges.sort()
    #print 'edges =', edges
    return nodes, edges

#----------------------------------------------------------------------

def show_grid(grid, strwidth):
    for row in grid:
        print(' '.join([str(k).zfill(strwidth) for k in row]))
    print()

pal = (
    b'\xff\x00\x00',
    b'\x00\xff\x00',
    b'\x00\x00\xff',
    b'\xff\xff\x00',
)

#----------------------------------------------------------------------

def main():
    if len(sys.argv) < 3:
        print ("Solve tromino grid puzzle\nUsage:\n"
        "%s width height [max_solutions]" % sys.argv[0])
        exit()

    width = int(sys.argv[1])
    height = int(sys.argv[2])
    maxcount = int(sys.argv[3]) if len(sys.argv) > 3 else 0
    ncolours = 4

    strwidth = len(str(width * height // 3 - 1))

    #Constants used for PPM output
    fnamebase = 'grid_%dx%d' % (width, height)
    scale = 16
    scalerange = range(scale)
    imgwidth, imgheight = scale * width, scale * height

    print('\nSolutions:')
    count = 1
    try:
        for grid in fill_grid(width, height):
            print('\n%2d:' % count)
            show_grid(grid, strwidth)
            nodes, edges = gridtograph(grid)

            #Find a colouring for this grid
            gen = colour_map(nodes, edges, ncolours=ncolours)
            solution = next(gen)
            colourmap = dict(solution)
            #print colourmap
            grid = [[colourmap[u] for u in row] for row in grid]
            #show_grid(grid, 1)

            #Convert to PPM
            data = []
            for row in grid:
                row = [u for u in row for _ in scalerange]
                data.extend(row * scale)
            ppmstr = b''.join([pal[u] for u in data])

            fname = '%s_%03d.ppm' % (fnamebase, count)
            with open(fname, 'wb') as f:
                f.write(b'P6\n%d %d\n255\n%s' % (imgwidth, imgheight, ppmstr))
            print('Saved to', fname)

            count += 1
            if maxcount and count > maxcount:
                break
        print(count - 1)
    except KeyboardInterrupt:
        print('\nAborted')


if __name__ == '__main__':
    main()

And here are the first 100 solutions for the 9 x 7 grid as an animated GIF.

These images all use 4 colours, however, it is possible to colour some of them with 3 colours.

(If the image doesn't animate for you, try your browser's "View Image Info" context menu item).

Answer 2

Here's an example I found by hand: