Tracing the mosaic

A museum floor is laid in lettered tiles. A guide claims a name is hidden in it, readable by walking from tile to touching tile. Check the claim.

The problem

The floor is a rectangle of tiles, each carrying one capital letter. A trace starts on any tile and steps to a tile sharing an edge — up, down, left or right, never diagonally. The letters visited, in order, spell the name. One tile may not be stood on twice within a trace, though a letter may repeat if the floor holds it on more than one tile.

Report whether the name can be traced at all: not where a trace starts, not how many exist.

Input. tiles — a list of equal-length strings, the rows of the floor from top to bottom. name — a string of capital letters.

Output. True if some trace spells the name, False otherwise.

Example. The floor for both examples is

R O S A
M T I L
A N E O

tiles = ["ROSA", "MTIL", "ANEO"], name = "ROSALIE"   ->  True

The trace runs along the top row to the A in the corner, drops to L, steps left to I, then down to E — seven tiles, each used once.

A second example, where a letter is present but unreachable:

tiles = ["ROSA", "MTIL", "ANEO"], name = "STONE"   ->  False

The only S touches O, A and I; no T is next to it. name = "ANA" is also False: the A and N in the bottom row touch, but the only way back to an A is the tile you are standing on.

Constraints.

• 1 <= len(tiles) <= 6
• 1 <= len(tiles[0]) <= 6, all rows the same length
• 1 <= len(name) <= 15
• Tiles and name are capital letters only.

Hints

Approach

Brute force

Enumerate every self-avoiding walk of the name's length from every tile and compare the letters at the end. A 6-by-6 floor has 36 starts and up to three onward choices per step, so a 15-letter name reaches about 36 · 3^14 walks — some 150 million, nearly all of them already wrong at the second letter.

The insight

Test the letter on arrival, not at the end: a tile whose letter is wrong ends the branch immediately, so the search only ever extends a prefix that is already correct.

The check is legal because the name is matched position by position along the path, so a mismatch at step k cannot be repaired later. The other precondition is the undo: on_path must mark exactly the tiles of the route being built, so a tile is cleared as its call returns — otherwise a failed route poisons every tile it touched for the routes tried after it.

Algorithm

1. For each tile, run walk(row, col, 0); answer True if any run succeeds.
2. In walk, return False if the tile's letter differs from name[k].
3. Return True if k is the last position — the name is complete.
4. Mark the tile as on the path.
5. Try the four edge neighbours that are inside the floor and unmarked; if any walk(neighbour, k + 1) succeeds, unmark and return True.
6. Unmark the tile and return False.

Complexity

Time O(r · c · 3^L) worst case, where L is the name's length — after the first step only three of the four neighbours are new. Space O(r · c + L) for the flags and the stack.

Solution

"""Tracing the mosaic — depth-first search over a grid, unmarking tiles on the way out."""


def solve(tiles, name):
    if not name:
        return True
    if not tiles or not tiles[0]:
        return False
    rows, cols = len(tiles), len(tiles[0])
    on_path = [[False] * cols for _ in range(rows)]

    def walk(r, c, k):
        if tiles[r][c] != name[k]:
            return False
        if k == len(name) - 1:
            return True
        # invariant: on_path marks exactly the tiles of the route built so far,
        # so a tile is never stepped on twice within one route
        on_path[r][c] = True
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not on_path[nr][nc]:
                if walk(nr, nc, k + 1):
                    on_path[r][c] = False
                    return True
        on_path[r][c] = False         # this route failed; the tile is free for other routes
        return False

    return any(walk(r, c, 0) for r in range(rows) for c in range(cols))


MOSAIC = ["ROSA", "MTIL", "ANEO"]

TESTS = [
    ((MOSAIC, "ROSALIE"), True),
    ((MOSAIC, "STONE"), False),
    ((MOSAIC, "ANA"), False),
    ((MOSAIC, "SIENA"), True),
    ((["Q"], "Q"), True),
    ((["Q"], "QQ"), False),
    ((MOSAIC, "TIN"), False),   # N is diagonal from I; edges only
    ((MOSAIC, "M"), True),
]

Pitfalls

• Never clearing the flag turns the search into one global visited set: ROSALIE may still pass, but a name needing a tile that an earlier dead end walked over comes back False.
• Allowing diagonal steps makes TIN traceable — N sits diagonally below I — when the floor only permits tiles that share an edge.
• Matching the letter before checking the bounds raises an IndexError at the floor's edges.

Variants

• Matching the moisture log — another two-index recursion, where the branching comes from the pattern rather than from the geometry.
• Bead kit bracelets — the same choose-recurse-undo skeleton when every branch reaches a valid answer.