El embaldosado de un $9\times 7$ rectángulo

Question

¿Puede un rectángulo $9\times 7$ se alicata mediante "bloques en L" (un bloque en L se compone de $3$ cuadrados de la unidad)?

Aunque el problema parece fácil, la coloración no me ayudó. La teoría general es interesante, pero busco una solución elemental y relativamente sencilla (adecuada para una olimpiada de secundaria).

Answer 1

Aquí hay un ejemplo que encontré a mano:

Answer 2

Aquí está el código Python para encontrar las soluciones de este rompecabezas para cualquier tamaño de cuadrícula. Las soluciones salen como texto y como archivos PPM. Este código fue probado en Python 2.6.6 pero debería funcionar correctamente en Python 2.5 o cualquier versión posterior.

#! /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()

Y aquí están las primeras 100 soluciones para la cuadrícula de 9 x 7 en forma de GIF animado.

Todas estas imágenes utilizan 4 colores, sin embargo, es es posible colorear algunas de ellas con 3 colores.

(Si la imagen no se anima, pruebe con la opción "Ver información de la imagen" del menú contextual de su navegador).